oj.uz

Submission #660571

# Submission time Handle Problem Language Result Execution time Memory
660571 2022-11-22T12:48:34 Z x0r Klasika (COCI20_klasika) C++17
44 / 110
 630 ms 250436 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[0] == 'A') {
            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 22288 KB Output is correct
2 Correct 12 ms 22312 KB Output is correct
3 Correct 11 ms 22528 KB Output is correct
4 Correct 11 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 11 ms 22400 KB Output is correct
7 Correct 11 ms 22356 KB Output is correct
8 Correct 11 ms 22452 KB Output is correct
9 Correct 11 ms 22484 KB Output is correct
10 Correct 11 ms 22448 KB Output is correct
11 Correct 11 ms 22468 KB Output is correct
12 Correct 12 ms 22424 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22288 KB Output is correct
2 Correct 12 ms 22312 KB Output is correct
3 Correct 11 ms 22528 KB Output is correct
4 Correct 11 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 11 ms 22400 KB Output is correct
7 Correct 11 ms 22356 KB Output is correct
8 Correct 11 ms 22452 KB Output is correct
9 Correct 11 ms 22484 KB Output is correct
10 Correct 11 ms 22448 KB Output is correct
11 Correct 11 ms 22468 KB Output is correct
12 Correct 12 ms 22424 KB Output is correct
13 Correct 13 ms 23188 KB Output is correct
14 Correct 13 ms 24016 KB Output is correct
15 Correct 14 ms 24556 KB Output is correct
16 Correct 14 ms 25700 KB Output is correct
17 Runtime error 28 ms 45044 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 206 ms 96744 KB Output is correct
2 Correct 281 ms 142444 KB Output is correct
3 Correct 343 ms 197808 KB Output is correct
4 Correct 363 ms 250436 KB Output is correct
5 Correct 259 ms 52380 KB Output is correct
6 Correct 367 ms 103888 KB Output is correct
7 Correct 473 ms 96052 KB Output is correct
8 Correct 630 ms 151184 KB Output is correct
9 Correct 203 ms 76056 KB Output is correct
10 Correct 294 ms 122312 KB Output is correct
11 Correct 352 ms 146616 KB Output is correct
12 Correct 413 ms 217540 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22288 KB Output is correct
2 Correct 12 ms 22312 KB Output is correct
3 Correct 11 ms 22528 KB Output is correct
4 Correct 11 ms 22612 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 11 ms 22400 KB Output is correct
7 Correct 11 ms 22356 KB Output is correct
8 Correct 11 ms 22452 KB Output is correct
9 Correct 11 ms 22484 KB Output is correct
10 Correct 11 ms 22448 KB Output is correct
11 Correct 11 ms 22468 KB Output is correct
12 Correct 12 ms 22424 KB Output is correct
13 Correct 13 ms 23188 KB Output is correct
14 Correct 13 ms 24016 KB Output is correct
15 Correct 14 ms 24556 KB Output is correct
16 Correct 14 ms 25700 KB Output is correct
17 Runtime error 28 ms 45044 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -