Submission #1212137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212137		Malix	Joker (BOI20_joker)	C++20	100 / 100	544 ms	19896 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,m,q;
pii a;
vi p,s,t,ans;
vector<pi> c,d,e;

pi parent(int x){
    if(p[x]==x)return {x,0};
    pi X=parent(p[x]);
    c.PB({x,p[x]});
    e.PB({x,t[x]});
    p[x]=X.F;
    t[x]^=X.S;
    return {p[x],t[x]};
}

bool merge(pi ed){
    int x=ed.F,y=ed.S;
    int u=x,v=y;
    pi X=parent(x),Y=parent(y);
    if(X.F==Y.F)return t[x]==t[y];
    x=X.F;y=Y.F;
    if(s[x]<s[y])swap(x,y);
    c.PB({y,p[y]});
    d.PB({x,s[x]});
    e.PB({y,t[y]});
    s[x]+=s[y];
    p[y]=x;
    t[y]=t[u]^t[v]^1;
    return 0;
}

void clr(int x,int y,int z){
    while(c.size()>x){
        p[c.back().F]=c.back().S;
        c.pop_back();
    }
    while(d.size()>y){
        s[d.back().F]=d.back().S;
        d.pop_back();
    }
    while(e.size()>z){
        t[e.back().F]=e.back().S;
        e.pop_back();
    }
}

void solve(int x1,int x2,int y1,int y2){
    if(x2<x1)return;
    int m=(x1+x2)/2;
    int pos=y2;
    bool f=0;
    int nm1=c.size(),nm2=d.size(),nm3=e.size();
    REP(i,x1,m)merge(a[i]);
    while(f==0&&y1<=pos)f|=merge(a[pos--]);
    ans[m]=pos;
    clr(nm1,nm2,nm3);
    pos++;
    if(x1==x2)return;
    nm1=c.size(),nm2=d.size(),nm3=e.size();
    REP(i,pos+1,y2+1)merge(a[i]);
    solve(x1,m-1,y1,pos);
    clr(nm1,nm2,nm3);
    nm1=c.size(),nm2=d.size(),nm3=e.size();
    REP(i,x1,m+1)merge(a[i]);
    solve(m+1,x2,pos,y2);
    clr(nm1,nm2,nm3);
}

int main() {   
ios::sync_with_stdio(0);
cin.tie(0);
    cin>>n>>m>>q;
    a.resize(m);
    p.resize(n);t.resize(n,0);s.resize(n,1);
    REP(i,0,n)p[i]=i;
    REP(i,0,m){
        int x,y;cin>>x>>y;
        x--;y--;
        a[i]={x,y};
    }
    ans.resize(m,-1);
    int k=m;
    bool fl=0;
    REP(i,0,m-1){
        fl|=merge(a[i]);
        if(fl){
            k=i;
            break;
        }
    }
    clr(0,0,0);
    REP(i,k+1,m)ans[i]=m-1;
    if(k>=0)solve(0,k,0,m-1);
    REP(i,0,q){
        int x,y;cin>>x>>y;
        x--;y--;
        if(ans[x]<y)cout<<"NO\n";
        else cout<<"YES\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