Submission #649749

#	Time	Username	Problem	Language	Result	Execution time	Memory
649749		DJeniUp	Joker (BOI20_joker)	C++17	0 / 100	0 ms	212 KiB

Joker

#include "bits/stdc++.h"
//#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 100000000007
#define endl '\n'
#define MOD 998244353
#define N 200007

ll n,m,q,p[N],t[N],res[N],h[N],f,k;

struct D{
    ll l,r;
}d[N];

ll H(ll x,ll z){
    ll r1=0;
    while(p[x]!=x && t[x]<=z){
        if(f==1)cout<<x<<" "<<p[x]<<" "<<t[x]<<" "<<h[x]<<endl;
        r1+=h[x];
        x=p[x];
    }
    return r1;
}

ll A(ll x){
    if(p[x]==x)return x;
    return A(p[x]);
}

ll S(ll x,ll y){
    if(A(x)!=A(y))return 0;
    if(H(x,INF)%2==H(y,INF)%2)return 2;
    return 1;
}

ll P(ll x,ll z){
    if(f==1)cout<<x<<" ! "<<z<<endl;
    if(t[x]>z || p[x]==x)return x;
    return P(p[x],z);
}

void Add(ll x,ll y,ll z,ll l1,ll r1){
    if(rand()%2){
        swap(x,y);
        swap(l1,r1);
    }
    ll x1=P(x,z);
    ll y1=P(y,z);
    l1+=H(x,z);
    r1+=H(y,z);
    //cout<<x<<" "<<y<<" "<<x1<<" "<<y1<<" "<<l1<<" "<<r1<<endl;
    if(p[x1]!=x1 && t[x1]<=k)Add(p[x1],y1,z,l1+1,r1);
    h[x1]=1+l1+r1;
    t[x1]=z;
    p[x1]=y1;
    return ;
}

int main(){
    
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>d[i].l>>d[i].r;
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        t[i]=INF;
    }
    ll x=1;
    for(int i=1;i<=m;i++){
        if(S(d[i].l,d[i].r)==0){
            Add(d[i].l,d[i].r,i,0,0);
        }else if(S(d[i].l,d[i].r)==2){
            x=i-1;
            break;
        }
    }
    //cout<<x<<endl;
    for(int i=x+1;i<=m;i++){
        res[i]=m+1;
    }
    for(int i=m;i>=1;i--){
        if(x==0)break;
        //if(i==7)f=1;
        cout<<d[i].l<<" "<<d[i].r<<" "<<P(d[i].l,x)<<" ! "<<P(d[i].r,x)<<" "<<H(d[i].l,x)<<" "<<H(d[i].r,x)<<" "<<x<<" "<<i<<endl;
        while(x>0 && P(d[i].l,x)==P(d[i].r,x) && H(d[i].l,x)%2==H(d[i].r,x)%2){
            cout<<d[i].l<<" "<<d[i].r<<" "<<P(d[i].l,x)<<" ! "<<P(d[i].r,x)<<" "<<H(d[i].l,x)<<" "<<H(d[i].r,x)<<" "<<x<<" "<<i<<endl;
            res[x]=i;
            x--;
            //cout<<x<<endl;
        }
        k=x;
        //if(f==1)break;
        //cout<<x<<endl;
        if(P(d[i].l,x)!=P(d[i].r,x))Add(d[i].l,d[i].r,0,0,0);
    }
    for(int i=1;i<=q;i++){
        ll x,y;
        cin>>x>>y;
        if(y>=res[x-1])cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    
    return 0;
}

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