제출 #1340725

#제출 시각아이디문제언어결과실행 시간메모리
1340725notbrainingJoker (BOI20_joker)C++20
0 / 100
334 ms32536 KiB
#include<iostream>
#include<vector>
#include<set>
#include<cassert>
using namespace std;
#define int long long
#define pii pair<int,int>
int n, m, q;
bool bipar[300000];
pii adj[300000];
struct dsu{
    vector<bool>col;
    vector<int>par;
    vector<set<int>>children;
    int n;
    dsu(int _){
        n = _ + 10;
        par = vector<int>(n + 1);
        col = vector<bool>(n + 1);
        children = vector<set<int>>(n + 1);
        for(int i = 0; i < n; ++i){
            col[i] = 1;
            par[i] = -1;
            children[i].insert(i);
        }

    }
    int get(int x){
        return (par[x] < 0 ? x : par[x] = get(par[x]));
    }
    bool sameset(int a, int b){
        return (get(a) == get(b));
    }
    bool uni(int a, int b){
        int fa_a = get(a); int fa_b = get(b);
        if(fa_a == fa_b){
            //just check if they have the same color or not
            return col[a] != col[b];
            //only a success if they have different colors
        }
        //do small to large merging if not same comp,
        //- smaller component changes all their colors if conflict, 
        // - big componenet gets smaller componen's colors
        if(par[fa_a] > par[fa_b]){
            swap(fa_a, fa_b);
        }
        //fa_a gets the elements from fa_b 's set
        if(col[a] == col[b]){
            for(int j : children[fa_b]){
                children[fa_a].insert(j);
                col[j] = (!col[j]);
            }
        }
        par[fa_a] += par[fa_b];
        par[fa_b] = fa_a;

        return true;
    }
};
int32_t main(){
    cin >> n >> m >> q;
    for(int i = 0; i < m; ++i){
        int a, b; cin >> a >> b;
        adj[i] = {a, b};
    }
    bool curr_bi = true;
    dsu D(n + 10);
    bipar[m] = true;
    for(int i = m - 1; i >= 0; --i){
        if(!D.uni(adj[i].first, adj[i].second)){
            curr_bi = false;
        }
        bipar[i] = curr_bi;
    }
    for(int i = 0; i < q; ++i){
        int l, r; cin >> l >> r; --l; --r;
        if(!bipar[r + 1]){
            cout << "YES\n";
        } else{
            cout << "NO\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...