When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Shadi_Bahaa's blog

By Shadi_Bahaa, history, 3 years ago, In English

Hi!

I tried to solve this problem using BFS technique, and it seems that my code has passed test cases of huge number of inputs. However, it didn't pass the test case number 12. I don't know what is the fault I fell in it, because I can't trace this test case as it contains huge number of inputs and at the same time not completely shown. If someone can find the logical problem in my code, I hope to tell me what it is.

Problem: https://codeforces.com/problemset/problem/580/C

My solution: https://codeforces.com/contest/580/submission/124986838

Edit (the correct code):

The problem was in pushing the nodes that passed the number of consecutives positions of cats m. The correct submission is here after one of the users found the problem, thanks to him!

corrected submission: https://codeforces.com/contest/580/submission/124994493

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The main problem is that you are taking those nodes into queue which are already having more than m consecutive cats in their path, the paths formed by them should never contribute to the answer.

Just put condition to check if number of consecutive cats till child node is less than or equal to m or not, then add that node to the queue.

Corrected Code

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
        int vis[100005]{};
        int n,m;
        cin>>n>>m;
        vector<int> id(n+1);
        vector<vector<int>> graph(n+1);
        for (int i =1 ;i<=n;i++){
            cin>>id[i];
        }
        int tmp = 1;
        for (int i = 0; i<n-1; i++){
            int x,y;
            cin>>x>>y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        int cnt = 0;
        queue<int> q;
        vector<int> no(n+1,0);
        q.push(1);
        vis[1]=1;
        if (id[1]==1){
            no[1]++;
        }
        while (q.size()){
            int ori = q.front();
            q.pop();
            if (id[ori]==0 && (graph[ori].size()!=1 || ori==1)){
                no[ori]=0;
            }
            for (int child:graph[ori]){
                if (!vis[child]){
                    vis[child] = 1;
                    no[child]=no[ori]+id[child];
                    if (graph[child].size()==1 && no[child]<=m){
                    ++cnt;
                    continue;
                    }
                    if(no[child]<=m)
                      q.push(child);
                }
     
            }
        }
        cout<<cnt<<endl;
    }