Submission #1288954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288954		nikolashami	Joker (BOI20_joker)	C++20	100 / 100	394 ms	20204 KiB

Joker

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

#pragma GCC optimize("O3")
const ll N=2e5+4;
array<ll,2>e[N];
ll f[N],ln[N],sz[N],ctp[N],ok,n,m,q;

stack<array<ll,6>>st;

ll fnd(ll x){
    return(ln[x]==x?x:fnd(ln[x]));
}

ll get(ll x){
    return(ln[x]==x?0:(ctp[x]^get(ln[x])));
}

void mrg(ll u,ll v){
    ll cU=get(u),cV=get(v);
    ll rU=fnd(u),rV=fnd(v);
    st.push({rU,rV,ln[rU],ctp[rU],sz[rV],ok});
    if(rU==rV){
        if(cU==cV)ok=0;
        return;
    }
    if(sz[rU]>sz[rV]){
        swap(rU,rV);
        swap(cU,cV);
    }
    st.pop();
    st.push({rU,rV,ln[rU],ctp[rU],sz[rV],ok});
    ln[rU]=rV;
    ctp[rU]=cU^cV^1;
    sz[rV]+=sz[rU];
}

void rollback(){
    auto[rU,rV,lnU,ctpU,szV,Ok]=st.top();
    st.pop();
    ln[rU]=lnU;
    ctp[rU]=ctpU;
    sz[rV]=szV;
    ok=Ok;
}

void dq(ll l=1,ll r=m,ll tl=1){
    if(l>r)return;
    //cout<<l<<' '<<r<<endl;
    //van [tl,r]
    ll md=(l+r)/2;
    for(int i=r;i>md;--i)mrg(e[i][0],e[i][1]);
    //
    if(!ok)f[md]=tl;
    for(int i=tl;ok&&i<=md;++i){
        mrg(e[i][0],e[i][1]);
        if(!ok)f[md]=i+1;
    }
    //cout<<l<<' '<<r<<' '<<md<<' '<<f[md]<<' '<<tl<<' '<<tr<<endl;
    for(int i=tl;i<f[md];++i)rollback();
    for(int i=r;i>md;--i)rollback();

    //cout<<f[md]<<' '<<md<<endl;

    for(int i=r;i>md-1;--i)mrg(e[i][0],e[i][1]);
    dq(l,md-1,tl);
    for(int i=r;i>md-1;--i)rollback();
    for(int i=tl;i<f[md];++i)mrg(e[i][0],e[i][1]);
    dq(md+1,r,f[md]);
    for(int i=tl;i<f[md];++i)rollback();
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>q;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        e[i]={u,v};
        f[i]=1+i;
    }

    iota(ln,ln+N,0);
    fill(sz,sz+N,1);
    ok=1;
    dq();
    assert(st.empty());

    //for(int i=1;i<=m;++i)
    //    cout<<f[i]<<' '<<i<<endl;
    
    while(q--){
        ll l,r;
        cin>>l>>r;
        cout<<(l>=f[r]?"YES\n":"NO\n");
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 22 / 22
• Subtask 5: 29 / 29
• Subtask 6: 6 / 6