oj.uz

Submission #877276

# Submission time Handle Problem Language Result Execution time Memory
877276 2023-11-23T05:18:41 Z socpite Joker (BOI20_joker) C++14
14 / 100
 2000 ms 11224 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 5e5 + 5;
 
int up[maxn], par[maxn];
 
int n, m, q;
 
int Find(int x){
    if(!up[x])return x;
    else{
        int tmp = up[x];
        up[x] = Find(tmp);
        par[x]^=par[tmp];
        return up[x];
    }
}
 
bool bad = 0;
 
vector<int> undo;
 
void Union(int a, int b){
    undo.push_back(a);
    undo.push_back(b);
    int ra = Find(a), rb = Find(b);
    if(ra == rb){
        // cout << ra << endl;
        // cout << par[a] << " " << par[b] << endl;
        if(par[a] == par[b])bad = 1;
    }
    else{
        up[rb]= ra;
        par[rb]=par[a]^par[b]^1;
    }
}
 
void rs() {
    bad = 0;
    for(auto v: undo)up[v] = par[v] = 0;
    undo.clear();
}
 
int U[maxn], V[maxn];
int bound[maxn];
 
void dnc(int l, int r, int ql, int qr) {
    if(l > r)return;
    int mid = (l+r)>>1;
    // cout << mid << " " << ql << " " << qr << endl;
    rs();
    int ans = qr;
    if(max(ql, mid) < qr) {
        if(ql > mid){
            for(int i = mid; i < ql; i++)Union(U[i], V[i]);
        }
        for(int i = max(mid, ql); i < qr; i++){
            Union(U[i], V[i]);
            if(bad){
                ans = i;
                break;
            }
        }
    }
    // cout << ans << endl;
    bound[mid] = ans;
    dnc(l, mid-1, ql, ans);
    dnc(mid+1, r, ans, qr);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)cin >> U[i] >> V[i];
    for(int i = m+1; i <= 2*m; i++){
        U[i] = U[i-m];
        V[i] = V[i-m];
    }
    dnc(1, m+1, 1, 2*m+1);
    // for(int i = 1; i <= 2*m; i++)cout << i << " " << bound[i] << endl;
    while(q--){
        int l, r;
        cin >> l >> r;
        if(l + m - 1 >= bound[r+1])cout << "YES";
        else cout << "NO";
        cout << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6580 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6620 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6496 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6580 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6620 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6496 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6564 KB Output is correct
30 Correct 3 ms 6492 KB Output is correct
31 Correct 3 ms 6496 KB Output is correct
32 Correct 4 ms 6640 KB Output is correct
33 Correct 2 ms 6636 KB Output is correct
34 Correct 3 ms 6492 KB Output is correct
35 Correct 4 ms 6708 KB Output is correct
36 Correct 16 ms 6704 KB Output is correct
37 Correct 13 ms 6724 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 3 ms 6492 KB Output is correct
40 Correct 2 ms 6632 KB Output is correct
41 Correct 3 ms 6580 KB Output is correct
42 Correct 2 ms 6492 KB Output is correct
43 Correct 3 ms 6492 KB Output is correct
44 Correct 3 ms 6496 KB Output is correct
45 Correct 5 ms 6496 KB Output is correct
46 Correct 4 ms 6496 KB Output is correct
47 Correct 3 ms 6488 KB Output is correct
48 Correct 5 ms 6504 KB Output is correct
49 Correct 3 ms 6496 KB Output is correct
50 Correct 4 ms 6760 KB Output is correct
51 Correct 3 ms 6504 KB Output is correct
52 Correct 3 ms 6504 KB Output is correct
53 Correct 3 ms 6500 KB Output is correct
54 Correct 4 ms 6504 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Execution timed out 2094 ms 11224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6580 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6620 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6496 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Execution timed out 2094 ms 11224 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6580 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6620 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6496 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6564 KB Output is correct
30 Correct 3 ms 6492 KB Output is correct
31 Correct 3 ms 6496 KB Output is correct
32 Correct 4 ms 6640 KB Output is correct
33 Correct 2 ms 6636 KB Output is correct
34 Correct 3 ms 6492 KB Output is correct
35 Correct 4 ms 6708 KB Output is correct
36 Correct 16 ms 6704 KB Output is correct
37 Correct 13 ms 6724 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 3 ms 6492 KB Output is correct
40 Correct 2 ms 6632 KB Output is correct
41 Correct 3 ms 6580 KB Output is correct
42 Correct 2 ms 6492 KB Output is correct
43 Correct 3 ms 6492 KB Output is correct
44 Correct 3 ms 6496 KB Output is correct
45 Correct 5 ms 6496 KB Output is correct
46 Correct 4 ms 6496 KB Output is correct
47 Correct 3 ms 6488 KB Output is correct
48 Correct 5 ms 6504 KB Output is correct
49 Correct 3 ms 6496 KB Output is correct
50 Correct 4 ms 6760 KB Output is correct
51 Correct 3 ms 6504 KB Output is correct
52 Correct 3 ms 6504 KB Output is correct
53 Correct 3 ms 6500 KB Output is correct
54 Correct 4 ms 6504 KB Output is correct
55 Execution timed out 2037 ms 10928 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6580 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6620 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6496 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6564 KB Output is correct
30 Correct 3 ms 6492 KB Output is correct
31 Correct 3 ms 6496 KB Output is correct
32 Correct 4 ms 6640 KB Output is correct
33 Correct 2 ms 6636 KB Output is correct
34 Correct 3 ms 6492 KB Output is correct
35 Correct 4 ms 6708 KB Output is correct
36 Correct 16 ms 6704 KB Output is correct
37 Correct 13 ms 6724 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 3 ms 6492 KB Output is correct
40 Correct 2 ms 6632 KB Output is correct
41 Correct 3 ms 6580 KB Output is correct
42 Correct 2 ms 6492 KB Output is correct
43 Correct 3 ms 6492 KB Output is correct
44 Correct 3 ms 6496 KB Output is correct
45 Correct 5 ms 6496 KB Output is correct
46 Correct 4 ms 6496 KB Output is correct
47 Correct 3 ms 6488 KB Output is correct
48 Correct 5 ms 6504 KB Output is correct
49 Correct 3 ms 6496 KB Output is correct
50 Correct 4 ms 6760 KB Output is correct
51 Correct 3 ms 6504 KB Output is correct
52 Correct 3 ms 6504 KB Output is correct
53 Correct 3 ms 6500 KB Output is correct
54 Correct 4 ms 6504 KB Output is correct
55 Execution timed out 2094 ms 11224 KB Time limit exceeded
56 Halted 0 ms 0 KB -