oj.uz

Submission #889567

# Submission time Handle Problem Language Result Execution time Memory
889567 2023-12-20T02:46:53 Z dimashhh Klasika (COCI20_klasika) C++17
110 / 110
 2134 ms 442520 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1, MOD = 998244353,b = 30;
typedef long long ll;
vector<array<int,3>> qr;
int q,tin[N],tout[N],n = 1,d[N],timer = 0;
vector<pair<int,int>> g[N];
void dfs(int v){
    tin[v] = ++timer;
    for(auto [to,w]:g[v]){
        d[to] = (d[v] ^ w);
        dfs(to);
    }
    tout[v] = ++timer;
}
struct node{
    node *next[2];
    set<int> st;
    node(){
        for(int i = 0;i < 2;i++){
            next[i] = nullptr;
        }
    }
};
node *root = new node();
void add(int tadd,int val){
    node *cur = root;
    cur->st.insert(tadd);
    for(int i = b;i >= 0;i--){
        int nv = ((val >> i) & 1);
        
        if(!cur->next[nv])
            cur->next[nv] = new node();
        cur = cur->next[nv];
        cur->st.insert(tadd);
    }
}
int get(int val,int l,int r){
    node *cur = root;
    if(cur->st.empty()) return 0;
    int ret = 0;
    for(int i = b;i >= 0;i--){
        int nd = ((val >> i) & 1);
        nd ^= 1;
        bool ok = false;
        if(cur->next[nd]){
            auto it = cur->next[nd]->st.lower_bound(l);
            if(it != cur->next[nd]->st.end() && *it <= r){
                ok = 1;
            }
        }
        if(ok){
            ret += (1ll << i);
            cur = cur->next[nd];
        }else{
            cur = cur->next[!nd];
        }
    }
    return ret;
}
void test(){
    cin >> q;
    for(int i = 1;i <= q;i++){
        string tp;
        cin >> tp;
        if(tp[0] == 'A'){
            ++n;
            int x,y;
            cin >> x >> y;
            g[x].push_back({n,y});
            qr.push_back({1,n,y});
        }else{
            int x,y;
            cin >> x >> y;
            qr.push_back({2,x,y});
        }
    }
    dfs(1);
    add(tin[1],0);
    for(auto i:qr){
        if(i[0] == 1){
            add(tin[i[1]],d[i[1]]);
            // cout << tin[i[1]] << ' ' << d[i[1]] << "x\n";
        }else{
            // cout << d[i[1]] << ' ' << tin[i[2]] << ' ' << tout[i[2]] << '\n';
            cout << get(d[i[1]],tin[i[2]],tout[i[2]]) << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 2 ms 10896 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11356 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 2 ms 10896 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11356 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Correct 5 ms 13404 KB Output is correct
15 Correct 7 ms 14816 KB Output is correct
16 Correct 8 ms 15964 KB Output is correct
17 Correct 5 ms 12244 KB Output is correct
18 Correct 6 ms 13404 KB Output is correct
19 Correct 7 ms 14684 KB Output is correct
20 Correct 8 ms 15816 KB Output is correct
21 Correct 5 ms 12120 KB Output is correct
22 Correct 6 ms 13456 KB Output is correct
23 Correct 7 ms 14684 KB Output is correct
24 Correct 8 ms 15708 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 126960 KB Output is correct
2 Correct 792 ms 236432 KB Output is correct
3 Correct 1238 ms 336184 KB Output is correct
4 Correct 1672 ms 439332 KB Output is correct
5 Correct 524 ms 128372 KB Output is correct
6 Correct 955 ms 232396 KB Output is correct
7 Correct 1406 ms 333088 KB Output is correct
8 Correct 1892 ms 433284 KB Output is correct
9 Correct 492 ms 127264 KB Output is correct
10 Correct 878 ms 233472 KB Output is correct
11 Correct 1248 ms 335472 KB Output is correct
12 Correct 1597 ms 435112 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 2 ms 10896 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11356 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Correct 5 ms 13404 KB Output is correct
15 Correct 7 ms 14816 KB Output is correct
16 Correct 8 ms 15964 KB Output is correct
17 Correct 5 ms 12244 KB Output is correct
18 Correct 6 ms 13404 KB Output is correct
19 Correct 7 ms 14684 KB Output is correct
20 Correct 8 ms 15816 KB Output is correct
21 Correct 5 ms 12120 KB Output is correct
22 Correct 6 ms 13456 KB Output is correct
23 Correct 7 ms 14684 KB Output is correct
24 Correct 8 ms 15708 KB Output is correct
25 Correct 452 ms 126960 KB Output is correct
26 Correct 792 ms 236432 KB Output is correct
27 Correct 1238 ms 336184 KB Output is correct
28 Correct 1672 ms 439332 KB Output is correct
29 Correct 524 ms 128372 KB Output is correct
30 Correct 955 ms 232396 KB Output is correct
31 Correct 1406 ms 333088 KB Output is correct
32 Correct 1892 ms 433284 KB Output is correct
33 Correct 492 ms 127264 KB Output is correct
34 Correct 878 ms 233472 KB Output is correct
35 Correct 1248 ms 335472 KB Output is correct
36 Correct 1597 ms 435112 KB Output is correct
37 Correct 878 ms 131008 KB Output is correct
38 Correct 1346 ms 237128 KB Output is correct
39 Correct 1650 ms 342512 KB Output is correct
40 Correct 1820 ms 442520 KB Output is correct
41 Correct 948 ms 128408 KB Output is correct
42 Correct 1468 ms 232948 KB Output is correct
43 Correct 1831 ms 333860 KB Output is correct
44 Correct 2134 ms 432884 KB Output is correct
45 Correct 1031 ms 127924 KB Output is correct
46 Correct 1563 ms 233684 KB Output is correct
47 Correct 1797 ms 334384 KB Output is correct
48 Correct 1945 ms 436504 KB Output is correct