Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя prakash.4

WRONG ANSWER IN AKBAR , THE GREAT
Автор prakash.4, история, 4 года назад, По-английски

Could anyone please help me find out what's wrong in my code. I'm getting wrong answer. Probably i didn't understand the question properly.

This is the link to the question. https://www.spoj.com/problems/AKBAR/

Below is my code.

include<bits/stdc++.h>

using namespace std; void dfs(vector<vector> &city,vector &visited,int s,int strength,map<int,int> &soldier) { visited[s] = true; for(int i = 0; i < city[s].size(); ++i) { if(visited[city[s][i]] == false && strength > 0 && soldier.find(city[s][i]) == soldier.end()) dfs(city,visited,city[s][i],strength-1,soldier); } }

int main() { int t; scanf("%d",&t); while(t--) { int n,r,m; scanf("%d%d%d",&n,&r,&m); vector<vector> city(n+1); vector visited(n+1); while(r--) { int a,b; scanf("%d%d",&a,&b); city[a].push_back(b); city[b].push_back(a); } map<int,int> soldier; while(m--) { int k,s; scanf("%d%d",&k,&s); soldier.insert({k,s}); } for(auto it = soldier.begin(); it != soldier.end(); ++it) dfs(city,visited,it->first,it->second,soldier); int i; for(i = 1; i <= n; ++i) if(visited[i] == false) { printf("No\n"); break; } if(i > n) printf("Yes\n"); } return 0; }

Thanks.

  • Проголосовать: нравится
  • -30
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your code isn't fit for the bold part of the question. This program may output "Yes" when a city is protected by more than one soldiers.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I modified my code a little bit according to your comment. Please see if i did anything wrong. I'm still getting wrong answer.

    include<bits/stdc++.h>

    using namespace std; void dfs(vector<vector> &city,vector &visited,int s,int strength,map<int,int> &soldier) { visited[s] = true; for(int i = 0; i < city[s].size(); ++i) { if(visited[city[s][i]] == false && strength > 0 && soldier.find(city[s][i]) == soldier.end()) dfs(city,visited,city[s][i],strength-1,soldier); } }

    int main() { int t; scanf("%d",&t); while(t--) { int n,r,m; scanf("%d%d%d",&n,&r,&m); vector<vector> city(n+1); vector visited(n+1); while(r--) { int a,b; scanf("%d%d",&a,&b); city[a].push_back(b); city[b].push_back(a); } map<int,int> soldier; bool temp = false; while(m--) { int k,s; scanf("%d%d",&k,&s); if(soldier.find(k) != soldier.end()) temp = true; else soldier.insert({k,s}); } if(temp == true) printf("No\n"); else { for(auto it = soldier.begin(); it != soldier.end(); ++it) dfs(city,visited,it->first,it->second,soldier); int i; for(i = 1; i <= n; ++i) if(visited[i] == false) { printf("No\n"); break; } if(i > n) printf("Yes\n"); } } return 0; }

    Thanks.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You must check the duplicates of soldiers for all dfs visits(since soldiers protect them). Frankly speaking, It's difficult for me to tell the way to fix with words. You may make dfs function like this:

      void dfs(vector<vector<int>> &city, vector<int> &visited, int s, int strength, int soldierid, bool & duplicate) {
  if(visited[s] != 0 && visited[s] != soldierid) { duplicate = true; return; }
  visited[s] = soldierid;
  for(int i = 0; i < city[s].size(); ++i) {
    if(strength > 0)
      dfs(city, visited, city[s][i], strength - 1, soldierid, duplicate);
  }
}

      I mean, try filling visited with positive ids of soldiers(such as m+1). If a city is protected by two soldiers, two ids will override visited[s], executes duplicate = true. If it's protected by no ones, visited will have 0.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Let me write my best advice for you.

First, I'll explain with words. In the previous advice, I used "ids" instead of bool. This is to identify another soldier's visits. In this problem, dfs may make duplicated visits of one soldier(and this should be ignored).

Second, try reading this full code.

Spoiler

Notice: I didn't submit this, so this program may be not accepted.

Finally, if you don't understand what I said, (maybe it comes from my dirty English, or my answer is wrong!) I recommend you to leave this problem unsolved and to come back later. Also recommend drawing graph if you didn't.

→ Ответить