oj.uz

Submission #857120

# Submission time Handle Problem Language Result Execution time Memory
857120 2023-10-05T11:56:03 Z Jethro Klasika (COCI20_klasika) C++14
110 / 110
 2035 ms 447836 KB 
//Writed by: Jethro_
//----------------------
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

const int N = 2e5 + 10;
int n, node = 1, i, root, val, in[N], out[N], cnt = 0, Xor[N], LG = 31, cnt2 = 0;
vector<pair<int, int>> a[N];
pair<int, int> query[N];
string type[N];

void add() {
    cin >> n;
    for(i = 1; i <= n; ++i) {
        cin >> type[i];
        if(type[i] == "Add") {
            cin >> root >> val;
            a[++node].push_back({root, val});
            a[root].push_back({node, val});
            
            query[i] = {node, node};
            
        }else {
            cin >> root >> val;
            query[i] = {root, val};
        }
    }
}
void dfs(int u, int p) {
    in[u] = ++cnt;
    for(auto [v, w] : a[u]) {
        if(v == p) continue;
        Xor[v] = Xor[u] ^ w;
        dfs(v, u);
    }

    out[u] = cnt;
}
struct Trie{
    struct Node{
        Node* child[2];
        int exist, cnt;
        set<int> save;

        Node() {
            for (int i = 0; i < 2; i++) child[i] = NULL;
            exist = cnt = 0;
        }
    };
 
    int cur;
    Node* root;
    Trie() : cur(0) {
        root = new Node();
    };
    void ADD(int s, int id) {
        Node* p = root;
        int u = 0;

        for(int i = LG; i >= 0; --i) {
            int k = (s >> i) & 1;
            if(p->child[k] == NULL) {
                p->child[k] = new Node();
            }
            p = p->child[k];
            p->save.insert(in[id]);
        }
    }
    int get(int s, int l, int r) {
        int u = 0, res = 0;
        Node* p = root;
        for(int i = LG; i >= 0; --i) {
            int k = (s >> i) & 1;
            if(p->child[k ^ 1] != NULL){
                auto x = p->child[k ^ 1]->save.lower_bound(l);
                if(x != p->child[k ^ 1]->save.end() && (*x) <= r){
                    p = p->child[k ^ 1];
                    res += (1 << i);
                }else {
                    p = p->child[k];
                }
            }else {
                p = p->child[k];
            }
        }
       return res;
    }
} trie;
void solve() {

    dfs(1, 0);
    trie.ADD(0, 1);
    
    for(i = 1; i <= n; ++i) {
        auto [x, y] = query[i];
        if(type[i] == "Add") {
            trie.ADD(Xor[x], y);
        }else {
            int now = Xor[x];
            cout << trie.get(now, in[y], out[y]) << '\n';
        }
    }
}
int main() {

    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    add();
    solve();

}

Compilation message

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [v, w] : a[u]) {
      |              ^
klasika.cpp: In member function 'void Trie::ADD(int, int)':
klasika.cpp:61:13: warning: unused variable 'u' [-Wunused-variable]
   61 |         int u = 0;
      |             ^
klasika.cpp: In member function 'int Trie::get(int, int, int)':
klasika.cpp:73:13: warning: unused variable 'u' [-Wunused-variable]
   73 |         int u = 0, res = 0;
      |             ^
klasika.cpp: In function 'void solve()':
klasika.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |         auto [x, y] = query[i];
      |              ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 15192 KB Output is correct
3 Correct 5 ms 15196 KB Output is correct
4 Correct 3 ms 15452 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15220 KB Output is correct
8 Correct 4 ms 15452 KB Output is correct
9 Correct 3 ms 14960 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 3 ms 15452 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 15192 KB Output is correct
3 Correct 5 ms 15196 KB Output is correct
4 Correct 3 ms 15452 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15220 KB Output is correct
8 Correct 4 ms 15452 KB Output is correct
9 Correct 3 ms 14960 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 3 ms 15452 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Correct 6 ms 17500 KB Output is correct
15 Correct 7 ms 18780 KB Output is correct
16 Correct 8 ms 20056 KB Output is correct
17 Correct 5 ms 16220 KB Output is correct
18 Correct 6 ms 17500 KB Output is correct
19 Correct 7 ms 18780 KB Output is correct
20 Correct 8 ms 20056 KB Output is correct
21 Correct 5 ms 16220 KB Output is correct
22 Correct 6 ms 17500 KB Output is correct
23 Correct 7 ms 18780 KB Output is correct
24 Correct 8 ms 19804 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 129360 KB Output is correct
2 Correct 732 ms 236668 KB Output is correct
3 Correct 1129 ms 339864 KB Output is correct
4 Correct 1437 ms 443392 KB Output is correct
5 Correct 486 ms 127828 KB Output is correct
6 Correct 956 ms 232876 KB Output is correct
7 Correct 1322 ms 333916 KB Output is correct
8 Correct 1785 ms 435284 KB Output is correct
9 Correct 433 ms 127164 KB Output is correct
10 Correct 812 ms 233552 KB Output is correct
11 Correct 1169 ms 336192 KB Output is correct
12 Correct 1507 ms 436888 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 15192 KB Output is correct
3 Correct 5 ms 15196 KB Output is correct
4 Correct 3 ms 15452 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15220 KB Output is correct
8 Correct 4 ms 15452 KB Output is correct
9 Correct 3 ms 14960 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 3 ms 15452 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Correct 6 ms 17500 KB Output is correct
15 Correct 7 ms 18780 KB Output is correct
16 Correct 8 ms 20056 KB Output is correct
17 Correct 5 ms 16220 KB Output is correct
18 Correct 6 ms 17500 KB Output is correct
19 Correct 7 ms 18780 KB Output is correct
20 Correct 8 ms 20056 KB Output is correct
21 Correct 5 ms 16220 KB Output is correct
22 Correct 6 ms 17500 KB Output is correct
23 Correct 7 ms 18780 KB Output is correct
24 Correct 8 ms 19804 KB Output is correct
25 Correct 434 ms 129360 KB Output is correct
26 Correct 732 ms 236668 KB Output is correct
27 Correct 1129 ms 339864 KB Output is correct
28 Correct 1437 ms 443392 KB Output is correct
29 Correct 486 ms 127828 KB Output is correct
30 Correct 956 ms 232876 KB Output is correct
31 Correct 1322 ms 333916 KB Output is correct
32 Correct 1785 ms 435284 KB Output is correct
33 Correct 433 ms 127164 KB Output is correct
34 Correct 812 ms 233552 KB Output is correct
35 Correct 1169 ms 336192 KB Output is correct
36 Correct 1507 ms 436888 KB Output is correct
37 Correct 834 ms 133344 KB Output is correct
38 Correct 1224 ms 239980 KB Output is correct
39 Correct 1548 ms 345924 KB Output is correct
40 Correct 1712 ms 447836 KB Output is correct
41 Correct 933 ms 130788 KB Output is correct
42 Correct 1403 ms 235884 KB Output is correct
43 Correct 1685 ms 337412 KB Output is correct
44 Correct 2035 ms 438268 KB Output is correct
45 Correct 978 ms 130184 KB Output is correct
46 Correct 1428 ms 236892 KB Output is correct
47 Correct 1727 ms 338376 KB Output is correct
48 Correct 1858 ms 440504 KB Output is correct