Submission #1212111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212111		Malix	Joker (BOI20_joker)	C++20	0 / 100	252 ms	327680 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;
vector<ti> b;
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(){
    reverse(c.begin(),c.end());
    reverse(d.begin(),d.end());
    reverse(e.begin(),e.end());
    for(auto [u,v]:c)p[u]=v;
    for(auto [u,v]:d)s[u]=v;
    for(auto [u,v]:e)t[u]=v;
    c.clear();d.clear();e.clear();
}

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

int main() {   
ios::sync_with_stdio(0);
cin.tie(0);
    cin>>n>>m>>q;
    a.resize(m);b.resize(q);
    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=0;
    bool fl=0;
    REP(i,0,m-1){
        fl|=merge(a[i]);
        if(fl){
            k=i;
            break;
        }
    }
    clr();
    REP(i,k,m)ans[i]=m-1;
    solve(0,k-1,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: 0 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 0 / 6