제출 #1345150

#제출 시각아이디문제언어결과실행 시간메모리
1345150azra_gonulJoker (BOI20_joker)C++20
100 / 100
203 ms13908 KiB
#include"bits/stdc++.h"
using namespace std;
const int nMax = 2e5 + 7;
long long cnt = 0;
bool ans[nMax];
long long smL[nMax];
long long rnk[nMax];
long long eq[nMax];
long long par[nMax];
vector <array <long long , 2> > edges;
array <long long , 2 > tmp1;
stack <array <long long , 2 > > st;
pair <long long , long long> findPar(long long a, long long tmp){
    if(par[a] == a){
        tmp = (tmp ^ eq[a]);
        return make_pair(a , tmp);
    }
    return findPar(par[a] , tmp ^ eq[a]);
}


void rb(){
	long long piv = st.top()[0];
    if(piv == -1){
       	cnt = st.top()[1];
        st.pop();
        return;
    }
    eq[piv] = 0;
    rnk[par[piv]] -= rnk[piv];
    par[piv] = piv;
    st.pop();
}

bool uni(long long a , long long b){
    pair <long long , long long> fr = findPar(a , 0);
    pair <long long , long long> sec = findPar(b , 0);

    //cout << a << " " << b << " "<< fr.first << " " << sec.first << "\n";
    if(fr.first == sec.first){
    	tmp1[0] = -1;
    	tmp1[1] = cnt;
    	st.push(tmp1);
        if(fr.second == sec.second){
            cnt++;
            return false;
        }
        return true;
    }
    a = fr.first;
    b = sec.first;
    if(rnk[a] > rnk[b]){
        swap(a , b);
    }
    tmp1[0] = a;
    tmp1[1] = -1;
    st.push(tmp1);
    rnk[b] += rnk[a];
    eq[a] = 0;
    if(fr.second == sec.second){
        eq[a] = 1;
    }
    par[a] = b;

    return true;
}
void rollback(long long sz){
	while(st.size() > sz){
        rb();
    }
    
}
void dvC(long long l1 , long long l2 , long long r1 , long long r2){
    if(l1 > l2 || r2 < l2 || r2 < r1 || r1 < l1){
        return;
    }

    long long lm = (l1 + l2) / 2;

    long long tm = st.size();
    long long ans = r2;
    for(long long i = l1; lm > i; i++){
        uni(edges[i][0] , edges[i][1]);
    }
    //cout << cnt << " ";
    while(r1 <= ans && cnt == 0){
        ans--;
        uni(edges[ans][0] , edges[ans][1]);
    }
    
    ans = min(ans , r2);
   // cout << lm  << " " << ans << " " << cnt << "\n";
    smL[lm] = ans;
    rollback(tm);

    tm = st.size();
    for(long long i = ans; min((long long)edges.size() - 1 , r2) >= i; i++){
        uni(edges[i][0] , edges[i][1]);
    }
    dvC(l1 , lm - 1 , r1 , ans);
    rollback(tm);
    
    tm = st.size();
    for(long long i = l1; lm >= i; i++){
        uni(edges[i][0] , edges[i][1]);
    }
    dvC(lm + 1 , l2 , max(lm + 1 , ans) , r2);
    rollback(tm);
    

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long n , m , q , l , r;
    array <long long , 2> tmp;
    cin >> n >> m >> q;

    for(long long i = 1; n >= i; i++){
        rnk[i] = 1;
        par[i] = i;
    }
    tmp[0] = 0;
    tmp[1] = 0;

    edges.push_back(tmp);
    for(long long i = 0; m > i; i++){
        cin >> l >> r;
        tmp[0] = l;
        tmp[1] = r;
        edges.push_back(tmp);
    }
    dvC(1 , m , 1 , m + 1);
     for(long long i = 0; q > i; i++){
    	cin >>l >> r;
    	if(smL[l] > r){
    		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...