oj.uz

Submission #649798

# Submission time Handle Problem Language Result Execution time Memory
649798 2022-10-11T10:59:21 Z DJeniUp Joker (BOI20_joker) C++17
0 / 100
 201 ms 12240 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 Q{
    ll l,r;
}o[N];

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

set<ll>s;

ll P(ll x){
    if(p[x]!=x){
        ll g=P(p[x]);
        t[x]+=t[p[x]];
        p[x]=g;
    }
    return p[x];
}

ll H(ll x){
    ll r1=0;
    while(p[x]!=x){
        r1+=h[x];
        x=p[x];
    }
    return r1;
}

void A(ll x,ll y){
    if(rand()%2)swap(x,y);
    ll x1=P(x);
    ll y1=P(y);
    h[x1]=H(x)+1+H(y);
    p[x1]=y1;
    return ;
}

int main(){
    
    cin>>n>>m>>q;
    //s.insert(0);
    for(int i=1;i<=m;i++){
        cin>>d[i].l>>d[i].r;
    }
    for(int i=1;i<=q;i++){
        cin>>o[i].l>>o[i].r;
        s.insert(o[i].l-1);
    }
    for(auto it:s){
        res[it]=0;
        for(int i=1;i<=n;i++){
            p[i]=i;
            h[i]=0;
        }
        for(int i=1;i<=it;i++){
            if(P(d[i].l)!=P(d[i].r)){
                A(d[i].l,d[i].r);
            }else if(H(d[i].l)%2==H(d[i].r)%2){
                res[it]=m+1;
            }
        }
        if(res[it]!=0)continue;
        for(int i=m;i>=it;i--){
            if(P(d[i].l)==P(d[i].r) && H(d[i].l)%2==H(d[i].r)%2){
                res[it]=i;
                break;
            }else if(P(d[i].l)!=P(d[i].r))A(d[i].l,d[i].r);
        }
    }
    
    for(int i=1;i<=q;i++){
        
        if(res[o[i].l-1]>o[i].r)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 199 ms 10332 KB Output is correct
4 Correct 199 ms 12240 KB Output is correct
5 Incorrect 201 ms 11380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -