oj.uz

답안 #588531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588531 2022-07-03T13:18:59 Z leeh18 Klasika (COCI20_klasika) C++17
33 / 110
 775 ms 204808 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 {
            assert(check(bit, tin, tout));
            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

# 결과 실행 시간 메모리 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 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 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 6
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 60592 KB Output is correct
2 Correct 653 ms 110900 KB Output is correct
3 Correct 659 ms 156632 KB Output is correct
4 Correct 771 ms 204808 KB Output is correct
5 Correct 377 ms 58772 KB Output is correct
6 Correct 511 ms 107452 KB Output is correct
7 Correct 639 ms 151412 KB Output is correct
8 Correct 719 ms 197688 KB Output is correct
9 Correct 379 ms 58792 KB Output is correct
10 Correct 504 ms 108104 KB Output is correct
11 Correct 624 ms 152972 KB Output is correct
12 Correct 775 ms 199220 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 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 6
6 Halted 0 ms 0 KB -