oj.uz

Submission #1108865

# Submission time Handle Problem Language Result Execution time Memory
1108865 2024-11-05T12:17:49 Z AverageAmogusEnjoyer Joker (BOI20_joker) C++17
100 / 100
 1585 ms 24800 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

constexpr int nax = 200200,block_size = 450;
vector<tuple<int,int,int>> queries[block_size]; // r,l,idx
vector<bool> ans;
int edges[nax][2];
int n,m;

struct dsu_save {
    int x,y,lzx,lzy,szx,szy,parx,pary;
};

struct DSU {
    int lz[nax];
    int par[nax];
    int sz[nax];
    dsu_save stk[nax];
    int T = 0;
    DSU(int N) {
        for (int i = 0; i < N; i++)
            lz[i] = 0, par[i] = i, sz[i] = 1;
    }
    int get(int x,int &cx) {
        cx ^= lz[x];
        return (x == par[x] ? x : get(par[x],cx));
    }
    bool need_reset = 0;
    bool unite(int x,int y) {
        assert(!need_reset);

        // cout << "Adding edge: " << x + 1 << " " << y + 1 << endl;

        int cx = 0,cy = 0;
        int px = get(x,cx), py = get(y,cy);

        // cout << px + 1 << " " << py + 1 << " " << cx << " " << cy << endl;
        if (sz[px] < sz[py]) 
            swap(px,py);
        stk[T++] = {px,py,lz[px],lz[py],sz[px],sz[py],par[px],par[py]};
        if (cx == cy) {
            if (px == py) {
                need_reset = 1;
                return 1;
            } else {
                lz[py] ^= 1;
                sz[px] += sz[py];
                par[py] = px;
            }
        } else {
            if (px != py) {
                sz[px] += sz[py];
                par[py] = px;
            }
        }
        return 0;
    }
    void rollback(int k) {
        need_reset = 0;
        // do stuff
        assert(T >= k);
        while(k--) {
            auto &c = stk[--T];
            lz[c.x] = c.lzx,lz[c.y] = c.lzy,par[c.x] = c.parx,par[c.y] = c.pary,sz[c.x] = c.szx,sz[c.y] = c.szy;
        }
    }
};

DSU dsu(nax); 

bool solve_block(int block) {
    int current_r = m - 1;
    for (int i = max(0,(block - 1) * block_size); i < min(m,block * block_size); i++) {
        // cout << "edge index: " << i + 1 << endl;
        if (dsu.unite(edges[i][0],edges[i][1])) {
            for (int B = block; B < block_size; B++) 
                for (auto &[r,l,idx]: queries[B])
                    ans[idx] = 1;
            return 1;
        }
    }
    for (int i = 0; i < queries[block].size(); i++) {
        auto &[r,l,idx] = queries[block][i];
        while(current_r >= r) {
            // cout << "edge index: " << current_r + 1 << endl;
            if (dsu.unite(edges[current_r][0],edges[current_r][1])) {
                for (int j = i; j < queries[block].size(); j++) {
                    int idx2 = get<2>(queries[block][j]);
                    ans[idx2] = 1;
                }
                dsu.rollback(m - current_r); // potrebbero essere necessari dei +- 1
                return 0;
            }
            current_r--;
        }
        --l;
        int inserted = 0;
        while(l >= block * block_size) {
            // devo inserirlo
            inserted++;
            // cout << "edge index: " << l + 1 << endl;
            if (dsu.unite(edges[l][0],edges[l][1])) {
                ans[idx] = 1;
                break;
            }
            l--;
        }
        dsu.rollback(inserted);
    }
    dsu.rollback(m - current_r - 1);
    return 0;
}

vector<bool> trova_cicli(int N, int M, int Q, vector<int> A, vector<int> B, vector<int> L, vector<int> R) {
    n = N, m = M;
    for (int i = 0; i < M; i++)
        edges[i][0] = A[i],edges[i][1] = B[i];
    ans.resize(Q);
    for (int i = 0; i < Q; i++) 
        queries[L[i] / block_size].emplace_back(R[i],L[i],i);
    for (int i = 0; i < block_size; i++) 
        sort(queries[i].rbegin(),queries[i].rend());
    for (int i = 0; i < block_size; i++) 
        if (solve_block(i))
            break;
    return ans;
}

int main() {

    int N,M,Q;
    cin >> N >> M >> Q;
    vector<int> A(M),B(M),L(Q),R(Q);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        --A[i],--B[i];
    }
    for (int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i];
        --L[i];
    }
    auto res = trova_cicli(N,M,Q,A,B,L,R);
    for (int i = 0; i < Q; i++) 
        cout << (res[i] ? "YES" : "NO") << "\n";

}

Compilation message

Joker.cpp: In function 'bool solve_block(int)':
Joker.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < queries[block].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:92:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                 for (int j = i; j < queries[block].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 1 ms 4688 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct
15 Correct 2 ms 4688 KB Output is correct
16 Correct 2 ms 4688 KB Output is correct
17 Correct 2 ms 4688 KB Output is correct
18 Correct 2 ms 4740 KB Output is correct
19 Correct 2 ms 4688 KB Output is correct
20 Correct 2 ms 4688 KB Output is correct
21 Correct 2 ms 4688 KB Output is correct
22 Correct 1 ms 4688 KB Output is correct
23 Correct 2 ms 4688 KB Output is correct
24 Correct 2 ms 4688 KB Output is correct
25 Correct 2 ms 4688 KB Output is correct
26 Correct 2 ms 4708 KB Output is correct
27 Correct 2 ms 4688 KB Output is correct
28 Correct 1 ms 4688 KB Output is correct
29 Correct 6 ms 4688 KB Output is correct
30 Correct 6 ms 4688 KB Output is correct
31 Correct 5 ms 4688 KB Output is correct
32 Correct 4 ms 4688 KB Output is correct
33 Correct 3 ms 4688 KB Output is correct
34 Correct 7 ms 4860 KB Output is correct
35 Correct 7 ms 4856 KB Output is correct
36 Correct 5 ms 4688 KB Output is correct
37 Correct 6 ms 4856 KB Output is correct
38 Correct 7 ms 4836 KB Output is correct
39 Correct 6 ms 4688 KB Output is correct
40 Correct 5 ms 4756 KB Output is correct
41 Correct 5 ms 4688 KB Output is correct
42 Correct 4 ms 4688 KB Output is correct
43 Correct 3 ms 4688 KB Output is correct
44 Correct 3 ms 4688 KB Output is correct
45 Correct 5 ms 4700 KB Output is correct
46 Correct 3 ms 4688 KB Output is correct
47 Correct 6 ms 4760 KB Output is correct
48 Correct 5 ms 4856 KB Output is correct
49 Correct 6 ms 5276 KB Output is correct
50 Correct 5 ms 4736 KB Output is correct
51 Correct 5 ms 4844 KB Output is correct
52 Correct 4 ms 4756 KB Output is correct
53 Correct 5 ms 4856 KB Output is correct
54 Correct 5 ms 4688 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 153 ms 16936 KB Output is correct
4 Correct 156 ms 19236 KB Output is correct
5 Correct 156 ms 19128 KB Output is correct
6 Correct 158 ms 16932 KB Output is correct
7 Correct 158 ms 17080 KB Output is correct
8 Correct 152 ms 16928 KB Output is correct
9 Correct 147 ms 16936 KB Output is correct
10 Correct 155 ms 17080 KB Output is correct
11 Correct 178 ms 17088 KB Output is correct
12 Correct 199 ms 17080 KB Output is correct
13 Correct 159 ms 17080 KB Output is correct
14 Correct 160 ms 17080 KB Output is correct
15 Correct 169 ms 16932 KB Output is correct
16 Correct 167 ms 17080 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 1 ms 4688 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct
15 Correct 2 ms 4688 KB Output is correct
16 Correct 2 ms 4688 KB Output is correct
17 Correct 2 ms 4688 KB Output is correct
18 Correct 2 ms 4740 KB Output is correct
19 Correct 2 ms 4688 KB Output is correct
20 Correct 2 ms 4688 KB Output is correct
21 Correct 2 ms 4688 KB Output is correct
22 Correct 1 ms 4688 KB Output is correct
23 Correct 2 ms 4688 KB Output is correct
24 Correct 2 ms 4688 KB Output is correct
25 Correct 2 ms 4688 KB Output is correct
26 Correct 2 ms 4708 KB Output is correct
27 Correct 2 ms 4688 KB Output is correct
28 Correct 1 ms 4688 KB Output is correct
29 Correct 153 ms 16936 KB Output is correct
30 Correct 156 ms 19236 KB Output is correct
31 Correct 156 ms 19128 KB Output is correct
32 Correct 158 ms 16932 KB Output is correct
33 Correct 158 ms 17080 KB Output is correct
34 Correct 152 ms 16928 KB Output is correct
35 Correct 147 ms 16936 KB Output is correct
36 Correct 155 ms 17080 KB Output is correct
37 Correct 178 ms 17088 KB Output is correct
38 Correct 199 ms 17080 KB Output is correct
39 Correct 159 ms 17080 KB Output is correct
40 Correct 160 ms 17080 KB Output is correct
41 Correct 169 ms 16932 KB Output is correct
42 Correct 167 ms 17080 KB Output is correct
43 Correct 337 ms 17076 KB Output is correct
44 Correct 374 ms 19228 KB Output is correct
45 Correct 354 ms 19172 KB Output is correct
46 Correct 315 ms 16928 KB Output is correct
47 Correct 316 ms 16924 KB Output is correct
48 Correct 188 ms 16920 KB Output is correct
49 Correct 224 ms 17076 KB Output is correct
50 Correct 330 ms 17108 KB Output is correct
51 Correct 356 ms 17076 KB Output is correct
52 Correct 364 ms 17112 KB Output is correct
53 Correct 372 ms 16924 KB Output is correct
54 Correct 369 ms 17076 KB Output is correct
55 Correct 391 ms 17116 KB Output is correct
56 Correct 386 ms 17076 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 1 ms 4688 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct
15 Correct 2 ms 4688 KB Output is correct
16 Correct 2 ms 4688 KB Output is correct
17 Correct 2 ms 4688 KB Output is correct
18 Correct 2 ms 4740 KB Output is correct
19 Correct 2 ms 4688 KB Output is correct
20 Correct 2 ms 4688 KB Output is correct
21 Correct 2 ms 4688 KB Output is correct
22 Correct 1 ms 4688 KB Output is correct
23 Correct 2 ms 4688 KB Output is correct
24 Correct 2 ms 4688 KB Output is correct
25 Correct 2 ms 4688 KB Output is correct
26 Correct 2 ms 4708 KB Output is correct
27 Correct 2 ms 4688 KB Output is correct
28 Correct 1 ms 4688 KB Output is correct
29 Correct 6 ms 4688 KB Output is correct
30 Correct 6 ms 4688 KB Output is correct
31 Correct 5 ms 4688 KB Output is correct
32 Correct 4 ms 4688 KB Output is correct
33 Correct 3 ms 4688 KB Output is correct
34 Correct 7 ms 4860 KB Output is correct
35 Correct 7 ms 4856 KB Output is correct
36 Correct 5 ms 4688 KB Output is correct
37 Correct 6 ms 4856 KB Output is correct
38 Correct 7 ms 4836 KB Output is correct
39 Correct 6 ms 4688 KB Output is correct
40 Correct 5 ms 4756 KB Output is correct
41 Correct 5 ms 4688 KB Output is correct
42 Correct 4 ms 4688 KB Output is correct
43 Correct 3 ms 4688 KB Output is correct
44 Correct 3 ms 4688 KB Output is correct
45 Correct 5 ms 4700 KB Output is correct
46 Correct 3 ms 4688 KB Output is correct
47 Correct 6 ms 4760 KB Output is correct
48 Correct 5 ms 4856 KB Output is correct
49 Correct 6 ms 5276 KB Output is correct
50 Correct 5 ms 4736 KB Output is correct
51 Correct 5 ms 4844 KB Output is correct
52 Correct 4 ms 4756 KB Output is correct
53 Correct 5 ms 4856 KB Output is correct
54 Correct 5 ms 4688 KB Output is correct
55 Correct 298 ms 11424 KB Output is correct
56 Correct 1147 ms 13640 KB Output is correct
57 Correct 92 ms 13464 KB Output is correct
58 Correct 74 ms 11344 KB Output is correct
59 Correct 149 ms 11344 KB Output is correct
60 Correct 306 ms 11336 KB Output is correct
61 Correct 180 ms 11424 KB Output is correct
62 Correct 331 ms 11336 KB Output is correct
63 Correct 161 ms 11420 KB Output is correct
64 Correct 208 ms 11544 KB Output is correct
65 Correct 385 ms 11348 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 1 ms 4688 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct
15 Correct 2 ms 4688 KB Output is correct
16 Correct 2 ms 4688 KB Output is correct
17 Correct 2 ms 4688 KB Output is correct
18 Correct 2 ms 4740 KB Output is correct
19 Correct 2 ms 4688 KB Output is correct
20 Correct 2 ms 4688 KB Output is correct
21 Correct 2 ms 4688 KB Output is correct
22 Correct 1 ms 4688 KB Output is correct
23 Correct 2 ms 4688 KB Output is correct
24 Correct 2 ms 4688 KB Output is correct
25 Correct 2 ms 4688 KB Output is correct
26 Correct 2 ms 4708 KB Output is correct
27 Correct 2 ms 4688 KB Output is correct
28 Correct 1 ms 4688 KB Output is correct
29 Correct 6 ms 4688 KB Output is correct
30 Correct 6 ms 4688 KB Output is correct
31 Correct 5 ms 4688 KB Output is correct
32 Correct 4 ms 4688 KB Output is correct
33 Correct 3 ms 4688 KB Output is correct
34 Correct 7 ms 4860 KB Output is correct
35 Correct 7 ms 4856 KB Output is correct
36 Correct 5 ms 4688 KB Output is correct
37 Correct 6 ms 4856 KB Output is correct
38 Correct 7 ms 4836 KB Output is correct
39 Correct 6 ms 4688 KB Output is correct
40 Correct 5 ms 4756 KB Output is correct
41 Correct 5 ms 4688 KB Output is correct
42 Correct 4 ms 4688 KB Output is correct
43 Correct 3 ms 4688 KB Output is correct
44 Correct 3 ms 4688 KB Output is correct
45 Correct 5 ms 4700 KB Output is correct
46 Correct 3 ms 4688 KB Output is correct
47 Correct 6 ms 4760 KB Output is correct
48 Correct 5 ms 4856 KB Output is correct
49 Correct 6 ms 5276 KB Output is correct
50 Correct 5 ms 4736 KB Output is correct
51 Correct 5 ms 4844 KB Output is correct
52 Correct 4 ms 4756 KB Output is correct
53 Correct 5 ms 4856 KB Output is correct
54 Correct 5 ms 4688 KB Output is correct
55 Correct 153 ms 16936 KB Output is correct
56 Correct 156 ms 19236 KB Output is correct
57 Correct 156 ms 19128 KB Output is correct
58 Correct 158 ms 16932 KB Output is correct
59 Correct 158 ms 17080 KB Output is correct
60 Correct 152 ms 16928 KB Output is correct
61 Correct 147 ms 16936 KB Output is correct
62 Correct 155 ms 17080 KB Output is correct
63 Correct 178 ms 17088 KB Output is correct
64 Correct 199 ms 17080 KB Output is correct
65 Correct 159 ms 17080 KB Output is correct
66 Correct 160 ms 17080 KB Output is correct
67 Correct 169 ms 16932 KB Output is correct
68 Correct 167 ms 17080 KB Output is correct
69 Correct 337 ms 17076 KB Output is correct
70 Correct 374 ms 19228 KB Output is correct
71 Correct 354 ms 19172 KB Output is correct
72 Correct 315 ms 16928 KB Output is correct
73 Correct 316 ms 16924 KB Output is correct
74 Correct 188 ms 16920 KB Output is correct
75 Correct 224 ms 17076 KB Output is correct
76 Correct 330 ms 17108 KB Output is correct
77 Correct 356 ms 17076 KB Output is correct
78 Correct 364 ms 17112 KB Output is correct
79 Correct 372 ms 16924 KB Output is correct
80 Correct 369 ms 17076 KB Output is correct
81 Correct 391 ms 17116 KB Output is correct
82 Correct 386 ms 17076 KB Output is correct
83 Correct 298 ms 11424 KB Output is correct
84 Correct 1147 ms 13640 KB Output is correct
85 Correct 92 ms 13464 KB Output is correct
86 Correct 74 ms 11344 KB Output is correct
87 Correct 149 ms 11344 KB Output is correct
88 Correct 306 ms 11336 KB Output is correct
89 Correct 180 ms 11424 KB Output is correct
90 Correct 331 ms 11336 KB Output is correct
91 Correct 161 ms 11420 KB Output is correct
92 Correct 208 ms 11544 KB Output is correct
93 Correct 385 ms 11348 KB Output is correct
94 Correct 597 ms 17480 KB Output is correct
95 Correct 1585 ms 19948 KB Output is correct
96 Correct 499 ms 24800 KB Output is correct
97 Correct 349 ms 22600 KB Output is correct
98 Correct 374 ms 22344 KB Output is correct
99 Correct 208 ms 22344 KB Output is correct
100 Correct 305 ms 22556 KB Output is correct
101 Correct 453 ms 22424 KB Output is correct
102 Correct 577 ms 22664 KB Output is correct
103 Correct 800 ms 22600 KB Output is correct
104 Correct 387 ms 22600 KB Output is correct
105 Correct 555 ms 22656 KB Output is correct
106 Correct 735 ms 22600 KB Output is correct
107 Correct 467 ms 24760 KB Output is correct
108 Correct 803 ms 22520 KB Output is correct
109 Correct 830 ms 22384 KB Output is correct
110 Correct 866 ms 22344 KB Output is correct
111 Correct 838 ms 22468 KB Output is correct
112 Correct 835 ms 22344 KB Output is correct
113 Correct 815 ms 22468 KB Output is correct
114 Correct 832 ms 22492 KB Output is correct
115 Correct 833 ms 22428 KB Output is correct
116 Correct 846 ms 22440 KB Output is correct