oj.uz

Submission #649766

# Submission time Handle Problem Language Result Execution time Memory
649766 2022-10-11T10:41:56 Z DJeniUp Joker (BOI20_joker) C++17
0 / 100
 623 ms 147372 KB 
#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 T{
    ll p,t,h;
};

vector<ll>v[N];

stack<T>s[N];

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,max(z,t[x1]),l1+1,r1);
    v[z].pb(x1);
    s[x1].push({p[x1],t[x1],h[x1]});
    h[x1]=1+l1+r1+H(y,z);
    t[x1]=z;
    p[x1]=y1;
    return ;
}

void Add2(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,max(z,t[x1]),l1+1,r1);
    
    h[x1]=1+l1+r1+H(y,z);
    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;
            for(int j=0;j<v[x].size();j++){
                ll to=v[x][j];
                while(s[to].size()>0 && t[to]>=x){
                    p[to]=s[to].top().p;
                    t[to]=s[to].top().t;
                    h[to]=s[to].top().h;
                    s[to].pop();
                }
            }
            x--;
            //cout<<x<<endl;
        }
        k=x;
        //if(f==1)break;
        //cout<<x<<endl;
        if(P(d[i].l,x)!=P(d[i].r,x))Add2(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;
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for(int j=0;j<v[x].size();j++){
      |                         ~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Correct 80 ms 136496 KB Output is correct
4 Incorrect 80 ms 136524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Correct 80 ms 136496 KB Output is correct
4 Incorrect 80 ms 136524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Incorrect 623 ms 147372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Correct 80 ms 136496 KB Output is correct
4 Incorrect 80 ms 136524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Correct 80 ms 136496 KB Output is correct
4 Incorrect 80 ms 136524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 136508 KB Output is correct
2 Correct 80 ms 136504 KB Output is correct
3 Correct 80 ms 136496 KB Output is correct
4 Incorrect 80 ms 136524 KB Output isn't correct
5 Halted 0 ms 0 KB -