oj.uz

Submission #1017497

# Submission time Handle Problem Language Result Execution time Memory
1017497 2024-07-09T08:24:49 Z vjudge1 Klasika (COCI20_klasika) C++17
66 / 110
 489 ms 191060 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 2e5 + 10, LG = 31;
ll q, n = 2, par[N][LG], sp[N][LG], h[N];
ll sz = 1, nxt[N * 31][2];

int val[N], res, cur;
bool in_sub[2005][2005];
vector<pair<int, int>> g[N];

void dfs(int v, int b, int p = -1){
    if (in_sub[b][v])
        res = max(res, cur);
    for (auto [w, u] : g[v]){
        if (u == p) continue;
        cur ^= w;
        dfs(u, b, v);
        cur ^= w;
    }
}


void add(ll x){
    ll cur = 0;
    for (ll i = 30; i >= 0; i --){
        int b = (((1ll << i) & x) > 0);
        if (nxt[cur][b] == -1)
            nxt[cur][b] = sz++;
        cur = nxt[cur][b];
    }
}

ll get(ll x){
    ll cur = 0;
    ll res = 0;
    for (ll i = 30; i >= 0; i --){
        int b = (((1ll << i) & x) > 0);
        if (nxt[cur][1 - b] != -1){
            cur = nxt[cur][1 - b];
            res |= (1ll << i);
        }
        else
            cur = nxt[cur][b];
    }
    return res;
}

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);

    memset(par, -1, sizeof par);
    memset(nxt, -1, sizeof nxt);

    cin >> q;

    if (q <= 2000){
        int n = 1;
        in_sub[1][1] = 1;
        while (q--){
            string s;
            cin >> s;

            if (s[0] == 'A'){
                int x, y;
                cin >> x >> y;

                int v = ++n;
                par[v][0] = x;
                val[v] = y;

                int p = v;
                while (p != -1){
                    in_sub[p][v] = 1;
                    p = par[p][0];
                }

                g[x].push_back({y, v});
                g[v].push_back({y, x});
            }
            else{
                int a, b;
                cin >> a >> b;

                res = 0;
                cur = 0;
                dfs(a, b);

                cout << res << endl;
            }
        }

        return 0;
    }

    add(0);
    while (q--){
        string s;
        cin >> s;

        if (s == "Add"){
            ll x, y;
            cin >> x >> y;

            par[n][0] = x;
            sp[n][0] = y;

            for (ll i = 1; i < LG; i ++){
                if (par[n][i - 1] == -1) continue;
                par[n][i] = par[par[n][i - 1]][i - 1];
                sp[n][i] = sp[n][i - 1] ^ sp[par[n][i - 1]][i - 1];
            }
            h[n] = h[x] + 1;

            ll v = n;
            ll d = h[v] - h[1];
            ll val = 0;
            for (ll i = 0; i < LG; i ++){
                if ((1ll << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            add(val);
            // cout << "adding " << val << " in trie" << endl;

            n++;
        }
        else{
            ll a, b;
            cin >> a >> b;

            ll v = a;
            ll d = h[v] - h[1];
            ll val = 0;
            for (ll i = 0; i < LG; i ++){
                if ((1ll << i) & d){
                    val ^= sp[v][i];
                    v = par[v][i];
                }
            }

            // cout << "getting from " << val << endl; 
            cout << get(val) << endl;
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 150612 KB Output is correct
2 Correct 61 ms 150868 KB Output is correct
3 Correct 60 ms 150864 KB Output is correct
4 Correct 62 ms 150868 KB Output is correct
5 Correct 57 ms 150608 KB Output is correct
6 Correct 58 ms 150868 KB Output is correct
7 Correct 78 ms 150864 KB Output is correct
8 Correct 59 ms 151016 KB Output is correct
9 Correct 58 ms 150828 KB Output is correct
10 Correct 57 ms 150864 KB Output is correct
11 Correct 58 ms 150960 KB Output is correct
12 Correct 64 ms 150864 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 150612 KB Output is correct
2 Correct 61 ms 150868 KB Output is correct
3 Correct 60 ms 150864 KB Output is correct
4 Correct 62 ms 150868 KB Output is correct
5 Correct 57 ms 150608 KB Output is correct
6 Correct 58 ms 150868 KB Output is correct
7 Correct 78 ms 150864 KB Output is correct
8 Correct 59 ms 151016 KB Output is correct
9 Correct 58 ms 150828 KB Output is correct
10 Correct 57 ms 150864 KB Output is correct
11 Correct 58 ms 150960 KB Output is correct
12 Correct 64 ms 150864 KB Output is correct
13 Correct 65 ms 151592 KB Output is correct
14 Correct 79 ms 152404 KB Output is correct
15 Correct 71 ms 153292 KB Output is correct
16 Correct 69 ms 153836 KB Output is correct
17 Correct 66 ms 151436 KB Output is correct
18 Correct 63 ms 152148 KB Output is correct
19 Correct 84 ms 153172 KB Output is correct
20 Correct 79 ms 153780 KB Output is correct
21 Correct 67 ms 151380 KB Output is correct
22 Correct 85 ms 152192 KB Output is correct
23 Correct 66 ms 153196 KB Output is correct
24 Correct 63 ms 153856 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 162460 KB Output is correct
2 Correct 489 ms 172000 KB Output is correct
3 Correct 386 ms 181304 KB Output is correct
4 Correct 388 ms 191056 KB Output is correct
5 Correct 390 ms 162372 KB Output is correct
6 Correct 371 ms 172112 KB Output is correct
7 Correct 397 ms 181440 KB Output is correct
8 Correct 318 ms 191060 KB Output is correct
9 Correct 391 ms 162384 KB Output is correct
10 Correct 396 ms 172112 KB Output is correct
11 Correct 369 ms 181584 KB Output is correct
12 Correct 305 ms 191056 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 150612 KB Output is correct
2 Correct 61 ms 150868 KB Output is correct
3 Correct 60 ms 150864 KB Output is correct
4 Correct 62 ms 150868 KB Output is correct
5 Correct 57 ms 150608 KB Output is correct
6 Correct 58 ms 150868 KB Output is correct
7 Correct 78 ms 150864 KB Output is correct
8 Correct 59 ms 151016 KB Output is correct
9 Correct 58 ms 150828 KB Output is correct
10 Correct 57 ms 150864 KB Output is correct
11 Correct 58 ms 150960 KB Output is correct
12 Correct 64 ms 150864 KB Output is correct
13 Correct 65 ms 151592 KB Output is correct
14 Correct 79 ms 152404 KB Output is correct
15 Correct 71 ms 153292 KB Output is correct
16 Correct 69 ms 153836 KB Output is correct
17 Correct 66 ms 151436 KB Output is correct
18 Correct 63 ms 152148 KB Output is correct
19 Correct 84 ms 153172 KB Output is correct
20 Correct 79 ms 153780 KB Output is correct
21 Correct 67 ms 151380 KB Output is correct
22 Correct 85 ms 152192 KB Output is correct
23 Correct 66 ms 153196 KB Output is correct
24 Correct 63 ms 153856 KB Output is correct
25 Correct 417 ms 162460 KB Output is correct
26 Correct 489 ms 172000 KB Output is correct
27 Correct 386 ms 181304 KB Output is correct
28 Correct 388 ms 191056 KB Output is correct
29 Correct 390 ms 162372 KB Output is correct
30 Correct 371 ms 172112 KB Output is correct
31 Correct 397 ms 181440 KB Output is correct
32 Correct 318 ms 191060 KB Output is correct
33 Correct 391 ms 162384 KB Output is correct
34 Correct 396 ms 172112 KB Output is correct
35 Correct 369 ms 181584 KB Output is correct
36 Correct 305 ms 191056 KB Output is correct
37 Incorrect 443 ms 165796 KB Output isn't correct
38 Halted 0 ms 0 KB -