oj.uz

Submission #588528

# Submission time Handle Problem Language Result Execution time Memory
588528 2022-07-03T13:17:40 Z leeh18 Klasika (COCI20_klasika) C++17
33 / 110
 755 ms 208848 KB 
#include <bits/stdc++.h>
using namespace std;

struct graph {
    int n, timer;
    vector<vector<pair<int, int>>> adj;
    vector<int> dist, tin, tout;
    graph(int n_) : n(n_), timer(0), adj(n), dist(n), tin(n), tout(n) {}
    void add_edge(int parent, int node, int weight) {
        adj[parent].push_back({node, weight});
    }
    void dfs(int u = 0) {
        tin[u] = timer++;
        for (auto [v, w] : adj[u]) {
            dist[v] = dist[u] ^ w;
            dfs(v);
        }
        tout[u] = timer++;
    }
};

struct trie_node {
    array<unique_ptr<trie_node>, 2> children;
    vector<int> v;
    void insert(int x, int tin, int pos = 30) {
        if (pos < 0) return;
        int bit = (x >> pos) & 1;
        if (children[bit] == nullptr) {
            children[bit] = make_unique<trie_node>();
        }
        children[bit]->v.push_back(tin);
        children[bit]->insert(x, tin, pos-1);
    }
    bool check(int bit, int tin, int tout) {
        if (children[bit] == nullptr) return false;
        const auto &cv = children[bit]->v;
        auto lower_it = lower_bound(cv.begin(), cv.end(), tin);
        auto upper_it = upper_bound(cv.begin(), cv.end(), tout);
        return lower_it != upper_it;
    }
    int max_xor(int x, int tin, int tout, int pos = 30) {
        if (pos < 0) return 0;
        int ret = 0;
        int bit = (x >> pos) & 1;
        if (check(bit^1, tin, tout)) {
            ret = children[bit^1]->max_xor(x, tin, tout, pos-1);
            ret |= (1 << pos);
        } else {
            ret = children[bit]->max_xor(x, tin, tout, pos-1);
        }
        return ret;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int Q;
    cin >> Q;
    vector<tuple<int, int, int>> qs(Q);
    int cnt = 1;
    for (auto &[t, a, b] : qs) {
        string s;
        cin >> s >> a >> b;
        if (s == "Add") {
            t = 1;
            ++cnt;
            --a;
        } else {
            t = 2;
            --a;
            --b;
        }
    }
    graph g(cnt);
    int id = 0;
    for (auto &[t, a, b] : qs) {
        if (t == 1) {
            ++id;
            g.add_edge(a, id, b);
            b = id;
        }
    }
    g.dfs();
    trie_node trie;
    trie.insert(0, g.tin[0]);
    for (auto [t, a, b] : qs) {
        if (t == 1) {
            trie.insert(g.dist[b], g.tin[b]);
        } else {
            auto ans = trie.max_xor(g.dist[a], g.tin[b], g.tout[b]);
            cout << ans << '\n';
        }
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 63376 KB Output is correct
2 Correct 493 ms 114088 KB Output is correct
3 Correct 667 ms 160108 KB Output is correct
4 Correct 755 ms 208848 KB Output is correct
5 Correct 356 ms 61664 KB Output is correct
6 Correct 600 ms 110540 KB Output is correct
7 Correct 648 ms 154984 KB Output is correct
8 Correct 730 ms 201276 KB Output is correct
9 Correct 385 ms 61680 KB Output is correct
10 Correct 502 ms 111280 KB Output is correct
11 Correct 637 ms 156348 KB Output is correct
12 Correct 715 ms 203008 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -