oj.uz

Submission #689526

# Submission time Handle Problem Language Result Execution time Memory
689526 2023-01-28T17:16:08 Z danikoynov Klasika (COCI20_klasika) C++14
33 / 110
 844 ms 524288 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct trie
{
    trie *child[2];
    int depth;

    trie(int _depth)
    {
        depth = _depth;
        child[0] = child[1] = NULL;
    }
};

const int maxn = 200100;

struct query
{
    int x, y;
    string type;
}ask[maxn];

int n = 1, q;
vector < pair < int, int > > g[maxn];

int xor_depth[maxn], f[maxn], timer, tin[maxn], tout[maxn];
void dfs(int v)
{
    f[++ timer] = v;
    tin[v] = timer;

    for (pair < int, int > nb : g[v])
    {
        int u = nb.first;
        xor_depth[u] = (xor_depth[v] ^ nb.second);
        dfs(u);
    }

    tout[v] = timer;
}

trie *tree[4 * maxn];

void build_tree(int root, int left, int right)
{
    tree[root] = new trie(30);

    if (left == right)
        return;

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);
}

void add(trie *root, int &num)
{
    if (root -> depth < 0)
        return;

    int bit = ((1 << root -> depth) & num), type = (bit > 0);
    if (root -> child[type] == NULL)
        root -> child[type] = new trie(root -> depth - 1);

    add(root -> child[type], num);
}

int query_xor(trie *root, int x)
{
    if (root -> depth < 0)
        return 0;

    int bit = (1 << root -> depth), type = ((bit & x) > 0);
    if (root -> child[(type + 1) % 2] != NULL)
        return query_xor(root -> child[(type + 1) % 2], x) + bit;
    return query_xor(root -> child[type], x);
}

void update_node(int root, int val)
{
    add(tree[root], val);
}

void update(int root, int left, int right, int pos, int val)
{
    update_node(root, val);
    if (left == right)
        return;

    int mid = (left + right) / 2;
    if (pos <= mid)
        update(root * 2, left, mid, pos, val);
    else
        update(root * 2 + 1, mid + 1, right, pos, val);
}

int query_node(int root, int val)
{
    if (tree[root] -> child[0] == NULL &&
        tree[root] -> child[1] == NULL)
            return 0;
    return query_xor(tree[root], val);
}

int query_range(int root, int left, int right, int qleft, int qright, int val)
{

    if (left > qright || right < qleft)
        return 0;
    if (left >= qleft && right <= qright)
        return query_node(root, val);

    int mid = (left + right) / 2;
    return max(query_range(root * 2, left, mid, qleft, qright, val),
               query_range(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

void add_node(int ver)
{
    update(1, 1, n, tin[ver], xor_depth[ver]);
}

void solve()
{
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> ask[i].type >> ask[i].x >> ask[i].y;
        if (ask[i].type == "Add")
            g[ask[i].x].push_back({++ n, ask[i].y});

    }

    dfs(1);
    build_tree(1, 1, n);
    add_node(1);

    int ver_cnt = 1;
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == "Add")
        {
            add_node(++ ver_cnt);
        }
        else
        {

            int a = ask[i].x, b = ask[i].y;
            int ans = query_range(1, 1, n, tin[b], tout[b], xor_depth[a]);
            cout << ans << endl;
        }
    }
}

int main()
{
    ///speed();
    solve();
    return 0;
}
/**

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13140 KB Output is correct
2 Correct 7 ms 13324 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 10 ms 13908 KB Output is correct
5 Correct 7 ms 13000 KB Output is correct
6 Correct 10 ms 13268 KB Output is correct
7 Correct 9 ms 13600 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 8 ms 13092 KB Output is correct
10 Correct 8 ms 13476 KB Output is correct
11 Correct 10 ms 13696 KB Output is correct
12 Correct 8 ms 13908 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13140 KB Output is correct
2 Correct 7 ms 13324 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 10 ms 13908 KB Output is correct
5 Correct 7 ms 13000 KB Output is correct
6 Correct 10 ms 13268 KB Output is correct
7 Correct 9 ms 13600 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 8 ms 13092 KB Output is correct
10 Correct 8 ms 13476 KB Output is correct
11 Correct 10 ms 13696 KB Output is correct
12 Correct 8 ms 13908 KB Output is correct
13 Correct 14 ms 16340 KB Output is correct
14 Correct 24 ms 20268 KB Output is correct
15 Correct 22 ms 24480 KB Output is correct
16 Correct 25 ms 28328 KB Output is correct
17 Correct 13 ms 16084 KB Output is correct
18 Correct 18 ms 20052 KB Output is correct
19 Correct 31 ms 24240 KB Output is correct
20 Correct 35 ms 28148 KB Output is correct
21 Correct 13 ms 16212 KB Output is correct
22 Correct 17 ms 20012 KB Output is correct
23 Correct 21 ms 24148 KB Output is correct
24 Correct 27 ms 27988 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 499916 KB Output is correct
2 Runtime error 844 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13140 KB Output is correct
2 Correct 7 ms 13324 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 10 ms 13908 KB Output is correct
5 Correct 7 ms 13000 KB Output is correct
6 Correct 10 ms 13268 KB Output is correct
7 Correct 9 ms 13600 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 8 ms 13092 KB Output is correct
10 Correct 8 ms 13476 KB Output is correct
11 Correct 10 ms 13696 KB Output is correct
12 Correct 8 ms 13908 KB Output is correct
13 Correct 14 ms 16340 KB Output is correct
14 Correct 24 ms 20268 KB Output is correct
15 Correct 22 ms 24480 KB Output is correct
16 Correct 25 ms 28328 KB Output is correct
17 Correct 13 ms 16084 KB Output is correct
18 Correct 18 ms 20052 KB Output is correct
19 Correct 31 ms 24240 KB Output is correct
20 Correct 35 ms 28148 KB Output is correct
21 Correct 13 ms 16212 KB Output is correct
22 Correct 17 ms 20012 KB Output is correct
23 Correct 21 ms 24148 KB Output is correct
24 Correct 27 ms 27988 KB Output is correct
25 Correct 835 ms 499916 KB Output is correct
26 Runtime error 844 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -