oj.uz

Submission #660570

# Submission time Handle Problem Language Result Execution time Memory
660570 2022-11-22T12:47:05 Z x0r Klasika (COCI20_klasika) C++17
44 / 110
 602 ms 254092 KB 
#include <bits/stdc++.h>

#define int long long
#define pii pair < int, int >
#define fi first
#define se second

using namespace std;

const int INF = 2E9;

const int nmax = 4e5;

int q, timer = 1, len[nmax + 3], id = 0, res[nmax + 3], in[nmax + 3];

vector < int > adj[nmax + 3];

vector < pii > Query[nmax + 3];

struct Node {
    int child[2], val;
};

struct Trie_Tree {
    vector < pii > q;
    vector < Node > trie;
    void add_node() {
        Node tam;
        tam.child[0] = tam.child[1] = -1;
        tam.val = INF;
        trie.push_back(tam);
    }
    void insert(pii v) {
        q.push_back(v);
        int cur = 0;
        for (int i = 30; i >= 0; i--) {
            trie[cur].val = min(trie[cur].val, v.se);
            int bit = (v.fi >> i) & 1;
            if (trie[cur].child[bit] == -1) {
                add_node();
                trie[cur].child[bit] = trie.size() - 1;
            }
            cur = trie[cur].child[bit];
        }
        trie[cur].val = min(trie[cur].val, v.se);
    }
    void find_res(pii u) {
        int ans = 0;
        int cur = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (u.fi >> i) & 1;
            bit ^= 1;
            int nxt = trie[cur].child[bit];
            if (trie[nxt].val < u.se) {
                ans ^= (1 << i);
                cur = nxt;
            }
            else cur = trie[cur].child[bit ^ 1];
        }
        res[u.se] = ans;
    }
};

Trie_Tree dfs(int u) {
    Trie_Tree cur;
    cur.add_node();
    cur.insert({len[u], in[u]});
    //cout << u << " " << cur.q.size() << '\n';
    for (auto v : adj[u]) {
        Trie_Tree Q = dfs(v);
        if (cur.q.size() < Q.q.size())
            swap(cur, Q);
        for (auto x : Q.q)
            cur.insert(x);
    }
    // cout << u << '\n';
    // for (auto x : cur.q) cout << x.fi << " " << x.se << '\n';
    // cout << "//##############################################################################" << '\n';
    for (auto x : Query[u])
        cur.find_res(x);
    return cur;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> q;
    string s; int a, b;
    for (int i = 1; i <= q; i++) {
        cin >> s >> a >> b;
        if (s == "Add") {
            len[++ timer] = len[a] ^ b;
            in[timer] = i;
            adj[a].push_back(timer);
        }
        else Query[b].push_back({len[a], i});
    }
    memset(res, 255, sizeof(res));
    dfs(1);
    for (int i = 1; i <= q; i++)
        if (res[i] != -1) cout << res[i] << '\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22356 KB Output is correct
2 Correct 11 ms 22320 KB Output is correct
3 Correct 13 ms 22444 KB Output is correct
4 Correct 12 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 13 ms 22316 KB Output is correct
7 Correct 11 ms 22352 KB Output is correct
8 Correct 12 ms 22484 KB Output is correct
9 Correct 12 ms 22344 KB Output is correct
10 Correct 11 ms 22484 KB Output is correct
11 Correct 11 ms 22484 KB Output is correct
12 Correct 12 ms 22476 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22356 KB Output is correct
2 Correct 11 ms 22320 KB Output is correct
3 Correct 13 ms 22444 KB Output is correct
4 Correct 12 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 13 ms 22316 KB Output is correct
7 Correct 11 ms 22352 KB Output is correct
8 Correct 12 ms 22484 KB Output is correct
9 Correct 12 ms 22344 KB Output is correct
10 Correct 11 ms 22484 KB Output is correct
11 Correct 11 ms 22484 KB Output is correct
12 Correct 12 ms 22476 KB Output is correct
13 Correct 12 ms 23188 KB Output is correct
14 Correct 13 ms 24124 KB Output is correct
15 Correct 14 ms 24532 KB Output is correct
16 Correct 18 ms 25772 KB Output is correct
17 Runtime error 28 ms 45024 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 99552 KB Output is correct
2 Correct 277 ms 145588 KB Output is correct
3 Correct 321 ms 201228 KB Output is correct
4 Correct 385 ms 254092 KB Output is correct
5 Correct 283 ms 55188 KB Output is correct
6 Correct 394 ms 107060 KB Output is correct
7 Correct 487 ms 99556 KB Output is correct
8 Correct 602 ms 154788 KB Output is correct
9 Correct 223 ms 79016 KB Output is correct
10 Correct 289 ms 125496 KB Output is correct
11 Correct 404 ms 150056 KB Output is correct
12 Correct 442 ms 221260 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22356 KB Output is correct
2 Correct 11 ms 22320 KB Output is correct
3 Correct 13 ms 22444 KB Output is correct
4 Correct 12 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 13 ms 22316 KB Output is correct
7 Correct 11 ms 22352 KB Output is correct
8 Correct 12 ms 22484 KB Output is correct
9 Correct 12 ms 22344 KB Output is correct
10 Correct 11 ms 22484 KB Output is correct
11 Correct 11 ms 22484 KB Output is correct
12 Correct 12 ms 22476 KB Output is correct
13 Correct 12 ms 23188 KB Output is correct
14 Correct 13 ms 24124 KB Output is correct
15 Correct 14 ms 24532 KB Output is correct
16 Correct 18 ms 25772 KB Output is correct
17 Runtime error 28 ms 45024 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -