prakash.4's blog

WRONG ANSWER IN AKBAR , THE GREAT
By prakash.4, history, 5 years ago, In English

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.

  • Vote: I like it
  • -30
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply