oj.uz

Submission #768406

# Submission time Handle Problem Language Result Execution time Memory
768406 2023-06-28T05:37:00 Z DylanSmith Klasika (COCI20_klasika) C++17
33 / 110
 778 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) {
    int cur = 0, res = 0;
    for (int i = 29; i >= 0; i--) {
        if (cur == -1) continue;
        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 452 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 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 704 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 444 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 452 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 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 704 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 444 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 5 ms 2492 KB Output is correct
14 Correct 7 ms 4812 KB Output is correct
15 Correct 12 ms 7620 KB Output is correct
16 Correct 10 ms 10008 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 10 ms 9412 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 7364 KB Output is correct
24 Correct 9 ms 9280 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 303672 KB Output is correct
2 Runtime error 778 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 452 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 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 704 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 444 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 5 ms 2492 KB Output is correct
14 Correct 7 ms 4812 KB Output is correct
15 Correct 12 ms 7620 KB Output is correct
16 Correct 10 ms 10008 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 10 ms 9412 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 7364 KB Output is correct
24 Correct 9 ms 9280 KB Output is correct
25 Correct 513 ms 303672 KB Output is correct
26 Runtime error 778 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -