Diksha_goyal's blog

By Diksha_goyal, history, 20 months ago, In English
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?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Diksha_goyal, history, 3 years ago, In English

Given an array A of size n i.e., A = {A_1, A_2, ... A_n}

you are given K. you can choose any K integers (not necessarily from the given array)
i.e, X_1, X_2, X_3 .... X_K
Now, we define a function F for each A_i, such that F_i = min(abs(A_i - X_j)) where 1<= j <=K.

find the minimum value of F_1 + F_2 + .... F_n.

constraints:

1 <= n <= 10^5
1<= K <= n

Full text and comments »

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

By Diksha_goyal, history, 3 years ago, In English

I'm having a hard time understanding the editorial: https://atcoder.jp/contests/abc221/editorial/2732

for the problem: https://atcoder.jp/contests/abc221/tasks/abc221_e

I want to know how fen-wick tree is actually working in this problem. specially this block

for(int i=0; i<N; i++){
        ans += bit.sum(A[i])*modpow(2,i);
        ans %= mod;
        bit.add(A[i],modpow(div,i+1));
    }

I'm actually very new to CP and have no peers to seek help. So, I directly ask my problem through the blogs. please help me if you have an explanation to get me through it. Thanking you.

Full text and comments »

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