oj.uz

Submission #487599

# Submission time Handle Problem Language Result Execution time Memory
487599 2021-11-16T09:20:46 Z KazamaHoang Klasika (COCI20_klasika) C++14
110 / 110
 2337 ms 418160 KB 
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

struct Node {
    Node* nxt[2];
    set<int> s;
};

inline Node* create() {
    Node* res = new Node();
    for (int i = 0; i < 2; ++ i)
        res->nxt[i] = NULL;
    res->s.clear();
    return res;
}
    
int n = 1;
int numQuery;
pair<bool, pair<int, int>> qry[200005];
vector<int> adj[200005];
int in[200005], out[200005], timer = 0, Xor[200005];

Node* root = create();

inline int getbit(int x, int i) {
    return x >> i & 1;
}

inline void dfs(int u, int par = -1) {
    in[u] = ++ timer;
    for (int& v : adj[u])
        if (v != par) dfs(v, u);
    out[u] = timer;
}

inline void trie_insert(int x, int pos) {
    Node* cur = root;
    for (int i = 29; i >= 0; -- i) {
        int c = getbit(x, i);
        if (cur->nxt[c] == NULL) 
            cur->nxt[c] = create();
        cur = cur->nxt[c];
        cur->s.emplace(pos);
    }
}

inline int trie_get(int x, int u) {
    int res = 0;
    Node* cur = root;
    for (int i = 29; i >= 0; -- i) {
        int lf = 0, rt = 1;
        if (getbit(x, i)) swap(lf, rt);
        if (cur->nxt[rt] == NULL) { 
            cur = cur->nxt[lf];
        } else {
            auto it = cur->nxt[rt]->s.lower_bound(in[u]);
            if (it != cur->nxt[rt]->s.end() && *it <= out[u]) {
                res |= (1 << i);
                cur = cur->nxt[rt];
            } else {
                cur = cur->nxt[lf];
            }
        }
    }
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++ i) {
        string op;
        cin >> op >> qry[i].S.F >> qry[i].S.S;
        if (op == "Add") {
            qry[i].F = 0;
            int u = qry[i].S.F;
            int w = qry[i].S.S;
            int v = ++ n;
            Xor[v] = Xor[u] ^ w;
            adj[u].emplace_back(v);
            qry[i].S.F = v;
        } else qry[i].F = 1;
    }
    dfs(1);
    trie_insert(0, in[1]);
    for (int i = 1; i <= numQuery; ++ i) {
        if (!qry[i].F) {
            trie_insert(Xor[qry[i].S.F], in[qry[i].S.F]);
        } else {
            cout << trie_get(Xor[qry[i].S.F], qry[i].S.S) << "\n";
        }
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 5 ms 5452 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 5 ms 5452 KB Output is correct
13 Correct 8 ms 6348 KB Output is correct
14 Correct 7 ms 7628 KB Output is correct
15 Correct 9 ms 8808 KB Output is correct
16 Correct 12 ms 9932 KB Output is correct
17 Correct 6 ms 6296 KB Output is correct
18 Correct 7 ms 7500 KB Output is correct
19 Correct 9 ms 8716 KB Output is correct
20 Correct 10 ms 9804 KB Output is correct
21 Correct 6 ms 6300 KB Output is correct
22 Correct 7 ms 7588 KB Output is correct
23 Correct 10 ms 8780 KB Output is correct
24 Correct 14 ms 9828 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 117548 KB Output is correct
2 Correct 1079 ms 220180 KB Output is correct
3 Correct 1629 ms 318596 KB Output is correct
4 Correct 2085 ms 417596 KB Output is correct
5 Correct 681 ms 116032 KB Output is correct
6 Correct 1159 ms 217016 KB Output is correct
7 Correct 1610 ms 313968 KB Output is correct
8 Correct 2151 ms 410908 KB Output is correct
9 Correct 586 ms 115548 KB Output is correct
10 Correct 1075 ms 217820 KB Output is correct
11 Correct 1511 ms 316172 KB Output is correct
12 Correct 2023 ms 412712 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 5 ms 5452 KB Output is correct
13 Correct 8 ms 6348 KB Output is correct
14 Correct 7 ms 7628 KB Output is correct
15 Correct 9 ms 8808 KB Output is correct
16 Correct 12 ms 9932 KB Output is correct
17 Correct 6 ms 6296 KB Output is correct
18 Correct 7 ms 7500 KB Output is correct
19 Correct 9 ms 8716 KB Output is correct
20 Correct 10 ms 9804 KB Output is correct
21 Correct 6 ms 6300 KB Output is correct
22 Correct 7 ms 7588 KB Output is correct
23 Correct 10 ms 8780 KB Output is correct
24 Correct 14 ms 9828 KB Output is correct
25 Correct 653 ms 117548 KB Output is correct
26 Correct 1079 ms 220180 KB Output is correct
27 Correct 1629 ms 318596 KB Output is correct
28 Correct 2085 ms 417596 KB Output is correct
29 Correct 681 ms 116032 KB Output is correct
30 Correct 1159 ms 217016 KB Output is correct
31 Correct 1610 ms 313968 KB Output is correct
32 Correct 2151 ms 410908 KB Output is correct
33 Correct 586 ms 115548 KB Output is correct
34 Correct 1075 ms 217820 KB Output is correct
35 Correct 1511 ms 316172 KB Output is correct
36 Correct 2023 ms 412712 KB Output is correct
37 Correct 1186 ms 117952 KB Output is correct
38 Correct 1703 ms 219828 KB Output is correct
39 Correct 1980 ms 320908 KB Output is correct
40 Correct 2245 ms 418160 KB Output is correct
41 Correct 1207 ms 115836 KB Output is correct
42 Correct 1687 ms 216468 KB Output is correct
43 Correct 2045 ms 313828 KB Output is correct
44 Correct 2337 ms 409992 KB Output is correct
45 Correct 1271 ms 115500 KB Output is correct
46 Correct 1758 ms 217592 KB Output is correct
47 Correct 2061 ms 314696 KB Output is correct
48 Correct 2304 ms 412520 KB Output is correct