oj.uz

Submission #519706

# Submission time Handle Problem Language Result Execution time Memory
519706 2022-01-27T04:51:37 Z KoD Klasika (COCI20_klasika) C++17
110 / 110
 2610 ms 465064 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int LOG = 30;

struct Trie {
    struct Node {
        array<int, 2> child;
        std::set<int> set;
        Node() { child.fill(-1); }
    };
    int root;
    vector<Node> node;
    Trie() { root = add_node(); }
    int add_node() {
        node.emplace_back();
        return node.size() - 1;
    }
    void insert(const int i, const int x) {
        int u = root;
        for (int d = LOG - 1; d >= 0; --d) {
            const int k = x >> d & 1;
            if (node[u].child[k] == -1) {
                node[u].child[k] = add_node();
            }
            u = node[u].child[k];
            node[u].set.insert(i);
        }
    }
    int max(const int l, const int r, const int x) const {
        int u = root, ret = 0;
        for (int d = LOG - 1; d >= 0; --d) {
            const int k = x >> d & 1;
            const int good = node[u].child[k ^ 1];
            const int bad = node[u].child[k];
            if (good == -1) {
                u = bad;
            } else if (auto itr = node[good].set.lower_bound(l); itr != node[good].set.end() and *itr < r) {
                u = good;
                ret += 1 << d;
            } else {
                u = bad;
            }
        }
        return ret;
    }
};

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int Q;
    std::cin >> Q;
    int N = 1;
    vector<int> value(N);
    vector<vector<int>> graph(N);
    vector<pair<int, int>> query(Q);
    for (auto& [a, b] : query) {
        std::string s;
        std::cin >> s;
        if (s == "Add") {
            int x, y;
            std::cin >> x >> y;
            const int u = N++;
            value.push_back(y);
            graph.emplace_back();
            graph[x - 1].push_back(u);
            a = u, b = -1;
        } else {
            std::cin >> a >> b;
            a -= 1, b -= 1;
        }
    }
    vector<int> in(N), out(N);
    int stamp = 0;
    RecLambda([&](auto&& dfs, const int u, const int p) -> void {
        in[u] = stamp++;
        value[u] ^= value[p];
        for (const int v : graph[u]) {
            dfs(v, u);
        }
        out[u] = stamp;
    })(0, 0);
    Trie trie;
    trie.insert(in[0], value[0]);
    for (const auto& [a, b] : query) {
        if (b == -1) {
            trie.insert(in[a], value[a]);
        } else {
            std::cout << trie.max(in[b], out[b], value[a]) << '\n';
        }
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 676 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 676 KB Output is correct
13 Correct 3 ms 1812 KB Output is correct
14 Correct 5 ms 3236 KB Output is correct
15 Correct 6 ms 3616 KB Output is correct
16 Correct 8 ms 6372 KB Output is correct
17 Correct 5 ms 1740 KB Output is correct
18 Correct 5 ms 3236 KB Output is correct
19 Correct 6 ms 3488 KB Output is correct
20 Correct 7 ms 4384 KB Output is correct
21 Correct 3 ms 1740 KB Output is correct
22 Correct 5 ms 3236 KB Output is correct
23 Correct 6 ms 3488 KB Output is correct
24 Correct 7 ms 4504 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 113648 KB Output is correct
2 Correct 1183 ms 227788 KB Output is correct
3 Correct 1663 ms 280216 KB Output is correct
4 Correct 2259 ms 464872 KB Output is correct
5 Correct 716 ms 111540 KB Output is correct
6 Correct 1273 ms 223544 KB Output is correct
7 Correct 1800 ms 274540 KB Output is correct
8 Correct 2432 ms 456364 KB Output is correct
9 Correct 655 ms 111960 KB Output is correct
10 Correct 1203 ms 224380 KB Output is correct
11 Correct 1721 ms 276984 KB Output is correct
12 Correct 2284 ms 458236 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 676 KB Output is correct
13 Correct 3 ms 1812 KB Output is correct
14 Correct 5 ms 3236 KB Output is correct
15 Correct 6 ms 3616 KB Output is correct
16 Correct 8 ms 6372 KB Output is correct
17 Correct 5 ms 1740 KB Output is correct
18 Correct 5 ms 3236 KB Output is correct
19 Correct 6 ms 3488 KB Output is correct
20 Correct 7 ms 4384 KB Output is correct
21 Correct 3 ms 1740 KB Output is correct
22 Correct 5 ms 3236 KB Output is correct
23 Correct 6 ms 3488 KB Output is correct
24 Correct 7 ms 4504 KB Output is correct
25 Correct 649 ms 113648 KB Output is correct
26 Correct 1183 ms 227788 KB Output is correct
27 Correct 1663 ms 280216 KB Output is correct
28 Correct 2259 ms 464872 KB Output is correct
29 Correct 716 ms 111540 KB Output is correct
30 Correct 1273 ms 223544 KB Output is correct
31 Correct 1800 ms 274540 KB Output is correct
32 Correct 2432 ms 456364 KB Output is correct
33 Correct 655 ms 111960 KB Output is correct
34 Correct 1203 ms 224380 KB Output is correct
35 Correct 1721 ms 276984 KB Output is correct
36 Correct 2284 ms 458236 KB Output is correct
37 Correct 1008 ms 114056 KB Output is correct
38 Correct 1613 ms 228136 KB Output is correct
39 Correct 1985 ms 282592 KB Output is correct
40 Correct 2413 ms 465064 KB Output is correct
41 Correct 1182 ms 111876 KB Output is correct
42 Correct 1734 ms 223972 KB Output is correct
43 Correct 2184 ms 274900 KB Output is correct
44 Correct 2610 ms 456572 KB Output is correct
45 Correct 1234 ms 112264 KB Output is correct
46 Correct 1796 ms 224692 KB Output is correct
47 Correct 2167 ms 275720 KB Output is correct
48 Correct 2525 ms 458232 KB Output is correct