Atcoder: nearest black vertex

Revision en1, by Diksha_goyal, 2023-05-06 08:49:46
Your code here...

#include <bits/stdc++.h>
using namespace std;


int main(){
    int N, m;
    cin>>N>>m;
    vector<vector<int> > Graph(N);
    for(int i = 0; i<m; i++){
        int p, q;
        cin>>p>>q;
        --p, --q;
        Graph[p].emplace_back(q);
        Graph[q].emplace_back(p);
    }
    
    int K;
    cin>>K;
    string ans(N, '0');
    map<int, set<int> > M;
    set<int> colored_points;
    for(int i = 0; i<N; i++) colored_points.insert(i);
    while(K--){
        int p, d;
        cin>>p>>d;
        --p;
        pair<int, int> P = make_pair(p, 0);
        vector<int> vis(N, 0);
        vis[p] = 1;
        queue<pair<int, int> > Q;
        Q.push(P);
        while(!Q.empty()){
            P = Q.front();
            Q.pop();
            if(P.second==d){
                M[p].insert(P.first);
                //colored_points.insert(P.first);
            }
            else{
                if(P.second < d){
                    colored_points.erase(P.first);
                }
            }
            for(auto e: Graph[P.first]){
                if(!vis[e]){
                    vis[e] = 1;
                    Q.push(make_pair(e, P.second+1));
                }
            }
        }
    }
    
    for(auto e: M){
        if(e.second.size()==0){
            cout<<"NO\n";
            return 0;
        }
        int ok = 0;
        for(auto ee: e.second){
            
            if(colored_points.find(ee)!=colored_points.end()){
                ans[ee] = '1';
                ok = 1;
            }
        }
        if(!ok){
            cout<<"No\n";
            return 0;
        }
    }
    
    for(auto e: colored_points) ans[e] = '1';
    
    cout<<"Yes\n";
    cout<<ans<<'\n';
    
}





this is my solution to problem: https://atcoder.jp/contests/abc299/tasks/abc299_e

My logic is to colour all vertices black and then white if their distance is less than d for a given condition. Is that right? If it isn't, what's the issue, and if it is, where am I going wrong in my code?

Tags graphs, bfs, multisource bfs, atcoder, atcoder beginner, dfs and similar, algorithms, contest

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Diksha_goyal 2023-05-06 08:49:46 2165 Initial revision (published)