oj.uz

Submission #649803

# Submission time Handle Problem Language Result Execution time Memory
649803 2022-10-11T11:00:23 Z DJeniUp Joker (BOI20_joker) C++17
31 / 100
 2000 ms 14596 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],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]);
        h[x]+=h[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
6.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 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct

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 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 42 ms 488 KB Output is correct
30 Correct 71 ms 468 KB Output is correct
31 Correct 82 ms 532 KB Output is correct
32 Correct 82 ms 520 KB Output is correct
33 Correct 69 ms 520 KB Output is correct
34 Correct 80 ms 536 KB Output is correct
35 Correct 87 ms 528 KB Output is correct
36 Correct 62 ms 520 KB Output is correct
37 Correct 113 ms 536 KB Output is correct
38 Correct 164 ms 532 KB Output is correct
39 Incorrect 77 ms 524 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #3
25.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 228 ms 10052 KB Output is correct
4 Correct 207 ms 10872 KB Output is correct
5 Correct 212 ms 10124 KB Output is correct
6 Correct 211 ms 9260 KB Output is correct
7 Correct 217 ms 8828 KB Output is correct
8 Correct 193 ms 8396 KB Output is correct
9 Correct 198 ms 12184 KB Output is correct
10 Correct 200 ms 13964 KB Output is correct
11 Correct 243 ms 12916 KB Output is correct
12 Correct 294 ms 14596 KB Output is correct
13 Correct 229 ms 11296 KB Output is correct
14 Correct 224 ms 12128 KB Output is correct
15 Correct 274 ms 13360 KB Output is correct
16 Correct 226 ms 14480 KB Output is correct

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 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 228 ms 10052 KB Output is correct
30 Correct 207 ms 10872 KB Output is correct
31 Correct 212 ms 10124 KB Output is correct
32 Correct 211 ms 9260 KB Output is correct
33 Correct 217 ms 8828 KB Output is correct
34 Correct 193 ms 8396 KB Output is correct
35 Correct 198 ms 12184 KB Output is correct
36 Correct 200 ms 13964 KB Output is correct
37 Correct 243 ms 12916 KB Output is correct
38 Correct 294 ms 14596 KB Output is correct
39 Correct 229 ms 11296 KB Output is correct
40 Correct 224 ms 12128 KB Output is correct
41 Correct 274 ms 13360 KB Output is correct
42 Correct 226 ms 14480 KB Output is correct
43 Correct 1067 ms 13804 KB Output is correct
44 Execution timed out 2067 ms 14156 KB Time limit exceeded
45 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 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 42 ms 488 KB Output is correct
30 Correct 71 ms 468 KB Output is correct
31 Correct 82 ms 532 KB Output is correct
32 Correct 82 ms 520 KB Output is correct
33 Correct 69 ms 520 KB Output is correct
34 Correct 80 ms 536 KB Output is correct
35 Correct 87 ms 528 KB Output is correct
36 Correct 62 ms 520 KB Output is correct
37 Correct 113 ms 536 KB Output is correct
38 Correct 164 ms 532 KB Output is correct
39 Incorrect 77 ms 524 KB Output isn't correct
40 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 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 42 ms 488 KB Output is correct
30 Correct 71 ms 468 KB Output is correct
31 Correct 82 ms 532 KB Output is correct
32 Correct 82 ms 520 KB Output is correct
33 Correct 69 ms 520 KB Output is correct
34 Correct 80 ms 536 KB Output is correct
35 Correct 87 ms 528 KB Output is correct
36 Correct 62 ms 520 KB Output is correct
37 Correct 113 ms 536 KB Output is correct
38 Correct 164 ms 532 KB Output is correct
39 Incorrect 77 ms 524 KB Output isn't correct
40 Halted 0 ms 0 KB -