Submission #1299007

#TimeUsernameProblemLanguageResultExecution timeMemory
1299007efegJoker (BOI20_joker)C++20
0 / 100
292 ms9772 KiB
#include <bits/stdc++.h>
using namespace std; 


#define pb push_back
#define eb emplace_back
#define F first
#define S second

typedef pair<int,int> ii; 

template<typename T>
using vec = vector<T>; 
using i64 = long long; 

struct DSU{
    int n; 
    vec<int> dsu; 
    DSU(int n) : n(n){
        dsu.assign(n,-1); 
    }

    int find(int x){
        if (dsu[x] < 0) return x; 
        return dsu[x] = find(dsu[x]); 
    }

    bool merge(int x,int y){
        x = find(x); y = find(y); 
        if (x == y) return false; 
        if (dsu[x] > dsu[y]) swap(x,y); 
        dsu[x] += dsu[y]; 
        dsu[y] = x; 
        return true; 
    }
}; 

int n,m,q; 
vec<ii> edges; 
vec<vec<ii>> queries; 
vec<bool> ans; 

int main(){
    cin >> n >> m >> q;
    ans.assign(q + 1,false); 
    queries.assign(m,vec<ii>()); 

    for (int i = 0; i < m; i++){
        int a,b; cin >> a >> b; 
        a--; b--; 
        edges.eb(a,b); 
    }

    for (int i = 0; i < q; i++){
        int l,r; cin >> l >> r; 
        l--; r--; 
        queries[l].eb(r,i); 
    }

    for (int l = 0; l < m; l++){
        if (!queries[l].empty()){
            DSU dsu(n+1);
            bool ok = false; 
            for (int i = 0; i < l; i++){
                if (!dsu.merge(edges[i].F,edges[i].S)) ok = true;  
            } 
            
            int idx = m-1;
            while (!ok && idx >= l){
                if (!dsu.merge(edges[idx].F,edges[idx].S)) ok = true; 
                idx--;  
            }

            for (auto tp : queries[l]){
                int r,i; tie(r,i) = tp; 
                if (r <= idx) ans[i] = true;
                else ans[i] = false;  
            }
        }
    }

    for (int i = 0; i < q; i++) cout << (ans[i] ? "YES" : "NO") << endl; 


    return 0; 
}
#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...