oj.uz

Submission #857119

# Submission time Handle Problem Language Result Execution time Memory
857119 2023-10-05T11:55:36 Z Jethro Klasika (COCI20_klasika) C++17
33 / 110
 1152 ms 524288 KB 
//Writed by: Jethro_
//----------------------
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

const int N = 3e6 + 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 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;
      |             ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 169040 KB Output is correct
2 Correct 34 ms 169056 KB Output is correct
3 Correct 37 ms 169516 KB Output is correct
4 Correct 35 ms 169432 KB Output is correct
5 Correct 33 ms 168784 KB Output is correct
6 Correct 33 ms 169052 KB Output is correct
7 Correct 33 ms 169088 KB Output is correct
8 Correct 35 ms 169304 KB Output is correct
9 Correct 33 ms 168788 KB Output is correct
10 Correct 34 ms 169052 KB Output is correct
11 Correct 34 ms 169320 KB Output is correct
12 Correct 35 ms 169308 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 169040 KB Output is correct
2 Correct 34 ms 169056 KB Output is correct
3 Correct 37 ms 169516 KB Output is correct
4 Correct 35 ms 169432 KB Output is correct
5 Correct 33 ms 168784 KB Output is correct
6 Correct 33 ms 169052 KB Output is correct
7 Correct 33 ms 169088 KB Output is correct
8 Correct 35 ms 169304 KB Output is correct
9 Correct 33 ms 168788 KB Output is correct
10 Correct 34 ms 169052 KB Output is correct
11 Correct 34 ms 169320 KB Output is correct
12 Correct 35 ms 169308 KB Output is correct
13 Correct 36 ms 170064 KB Output is correct
14 Correct 38 ms 171608 KB Output is correct
15 Correct 38 ms 172628 KB Output is correct
16 Correct 40 ms 173912 KB Output is correct
17 Correct 36 ms 170076 KB Output is correct
18 Correct 37 ms 171384 KB Output is correct
19 Correct 40 ms 172636 KB Output is correct
20 Correct 39 ms 173884 KB Output is correct
21 Correct 36 ms 170072 KB Output is correct
22 Correct 38 ms 171352 KB Output is correct
23 Correct 42 ms 172624 KB Output is correct
24 Correct 42 ms 173888 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 285648 KB Output is correct
2 Correct 774 ms 394968 KB Output is correct
3 Correct 1145 ms 498448 KB Output is correct
4 Runtime error 1152 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 169040 KB Output is correct
2 Correct 34 ms 169056 KB Output is correct
3 Correct 37 ms 169516 KB Output is correct
4 Correct 35 ms 169432 KB Output is correct
5 Correct 33 ms 168784 KB Output is correct
6 Correct 33 ms 169052 KB Output is correct
7 Correct 33 ms 169088 KB Output is correct
8 Correct 35 ms 169304 KB Output is correct
9 Correct 33 ms 168788 KB Output is correct
10 Correct 34 ms 169052 KB Output is correct
11 Correct 34 ms 169320 KB Output is correct
12 Correct 35 ms 169308 KB Output is correct
13 Correct 36 ms 170064 KB Output is correct
14 Correct 38 ms 171608 KB Output is correct
15 Correct 38 ms 172628 KB Output is correct
16 Correct 40 ms 173912 KB Output is correct
17 Correct 36 ms 170076 KB Output is correct
18 Correct 37 ms 171384 KB Output is correct
19 Correct 40 ms 172636 KB Output is correct
20 Correct 39 ms 173884 KB Output is correct
21 Correct 36 ms 170072 KB Output is correct
22 Correct 38 ms 171352 KB Output is correct
23 Correct 42 ms 172624 KB Output is correct
24 Correct 42 ms 173888 KB Output is correct
25 Correct 454 ms 285648 KB Output is correct
26 Correct 774 ms 394968 KB Output is correct
27 Correct 1145 ms 498448 KB Output is correct
28 Runtime error 1152 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -