oj.uz

Submission #768407

# Submission time Handle Problem Language Result Execution time Memory
768407 2023-06-28T05:40:08 Z DylanSmith Klasika (COCI20_klasika) C++17
33 / 110
 616 ms 524288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

typedef struct Node {
    int adj[2], par; bool end;
    Node(int p = -1) {
        end = 0; par = p;
        fill(adj, adj + 2, -1);
    }
} node;

int add(vector<node> &tree, int n) {
    int cur = 0;
    for (int i = 29; i >= 0; i--) {
        if ((n & 1 << i) == 0) {
            if (tree[cur].adj[0] == -1) {
                tree[cur].adj[0] = sz(tree);
                tree.emplace_back(cur);
            }
            cur = tree[cur].adj[0];
        } else {
            if (tree[cur].adj[1] == -1) {
                tree[cur].adj[1] = sz(tree);
                tree.emplace_back(cur);
            }
            cur = tree[cur].adj[1];
        }
    }
    tree[cur].end = true;
    return cur;
}

int maxXor(vector<node> &tree, int n) {
    if (sz(tree) == 1) return 0;
    int cur = 0, res = 0;
    for (int i = 29; i >= 0; i--) {
        if ((n & 1 << i) > 0) {
            if (tree[cur].adj[0] != -1) {
                cur = tree[cur].adj[0];
                res ^= 1 << i;
            } else {
                cur = tree[cur].adj[1];
            }
        } else {
            if (tree[cur].adj[1] != -1) {
                cur = tree[cur].adj[1];
                res ^= 1 << i;
            } else {
                cur = tree[cur].adj[0];
            }
        }
    }
    return res;
}

void dfs(vector<vector<int>> &adj, vector<int> &tour, vector<int> &size, int u) {
    tour.pb(u);
    size[u] = 1;
    for (int v : adj[u]) {
        dfs(adj, tour, size, v);
        size[u] += size[v];
    }
}

void solve() {
    int Q; cin >> Q;
    vector<vector<int>> adj(1);
    vector<int> sum = {0};
    vector<vector<int>> queries;
    for (int q = 0; q < Q; q++) {
        string type; cin >> type;
        if (type == "Add") {
            int p, k; cin >> p >> k; p--;
            adj[p].pb(sz(adj));
            queries.pb({0, sz(adj)});
            adj.pb({});
            sum.pb(sum[p] ^ k);
        } else {
            int u, v; cin >> u >> v; u--; v--;
            queries.pb({1, u, v});
        }
    }
    int N = sz(adj);
    vector<int> tour, size(N);
    dfs(adj, tour, size, 0);
    vector<int> start(N);
    for (int i = 0; i < N; i++) {
        start[tour[i]] = i;
    }
    int M = 1; while (M < N) M <<= 1;
    vector<vector<node>> tree(M * 2);
    for (int i = 0; i < M * 2; i++) {
        tree[i] = vector<node>(1);
    }
    int n = M;
    while (n > 0) {
        add(tree[n], sum[0]);
        n >>= 1;
    }
    for (vector<int> query : queries) {
        if (query[0] == 0) {
            int u = query[1];
            n = start[u] + M;
            while (n > 0) {
                add(tree[n], sum[u]);
                n >>= 1;
            }
        } else {
            int u = query[1], v = query[2];
            int l = start[v] + M, r = l + size[v] - 1;
            int res = 0;
            while (l <= r) {
                if (l % 2 == 1) {
                    res = max(res, maxXor(tree[l], sum[u]));
                    l >>= 1;
                    l++;
                } else {
                    l >>= 1;
                }
                if (r % 2 == 0) {
                    res = max(res, maxXor(tree[r], sum[u]));
                    r >>= 1;
                    r--;
                } else {
                    r >>= 1;
                }
            }
            cout << res << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    solve();
 
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 4 ms 2512 KB Output is correct
14 Correct 6 ms 4808 KB Output is correct
15 Correct 8 ms 7620 KB Output is correct
16 Correct 10 ms 10004 KB Output is correct
17 Correct 4 ms 2388 KB Output is correct
18 Correct 6 ms 4812 KB Output is correct
19 Correct 8 ms 7364 KB Output is correct
20 Correct 12 ms 9392 KB Output is correct
21 Correct 4 ms 2388 KB Output is correct
22 Correct 6 ms 4812 KB Output is correct
23 Correct 8 ms 7320 KB Output is correct
24 Correct 10 ms 9324 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 302400 KB Output is correct
2 Runtime error 616 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 4 ms 2512 KB Output is correct
14 Correct 6 ms 4808 KB Output is correct
15 Correct 8 ms 7620 KB Output is correct
16 Correct 10 ms 10004 KB Output is correct
17 Correct 4 ms 2388 KB Output is correct
18 Correct 6 ms 4812 KB Output is correct
19 Correct 8 ms 7364 KB Output is correct
20 Correct 12 ms 9392 KB Output is correct
21 Correct 4 ms 2388 KB Output is correct
22 Correct 6 ms 4812 KB Output is correct
23 Correct 8 ms 7320 KB Output is correct
24 Correct 10 ms 9324 KB Output is correct
25 Correct 474 ms 302400 KB Output is correct
26 Runtime error 616 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -