oj.uz

Submission #689536

# Submission time Handle Problem Language Result Execution time Memory
689536 2023-01-28T17:27:40 Z danikoynov Klasika (COCI20_klasika) C++14
33 / 110
 867 ms 398852 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
{
    int depth, child[2];

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

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 * 40];
int last_used, root_index[maxn * 4];

void build_tree(int root, int left, int right)
{
    root_index[root] = ++ last_used;

    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(int root, int &num)
{
    if (tree[root].depth < 0)
        return;

    int bit = ((1 << tree[root].depth) & num), type = (bit > 0);
    if (tree[root].child[type] == -1)
    {
        tree[root].child[type] = ++ last_used;
        tree[last_used] = trie(tree[root].depth - 1);
    }

    add(tree[root].child[type], num);
}

int query_xor(int root, int x)
{
    if (tree[root].depth < 0)
        return 0;

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

void update_node(int root, int val)
{
    add(root_index[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)
{
    int idx = root_index[root];
    if (tree[idx].child[0] == -1 &&
        tree[idx].child[1] == -1)
            return 0;
    return query_xor(idx, 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 160 ms 388656 KB Output is correct
2 Correct 165 ms 388840 KB Output is correct
3 Correct 170 ms 388660 KB Output is correct
4 Correct 166 ms 388680 KB Output is correct
5 Correct 168 ms 388684 KB Output is correct
6 Correct 182 ms 388696 KB Output is correct
7 Correct 163 ms 388756 KB Output is correct
8 Correct 165 ms 388752 KB Output is correct
9 Correct 170 ms 388692 KB Output is correct
10 Correct 166 ms 388740 KB Output is correct
11 Correct 163 ms 388728 KB Output is correct
12 Correct 165 ms 388672 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 388656 KB Output is correct
2 Correct 165 ms 388840 KB Output is correct
3 Correct 170 ms 388660 KB Output is correct
4 Correct 166 ms 388680 KB Output is correct
5 Correct 168 ms 388684 KB Output is correct
6 Correct 182 ms 388696 KB Output is correct
7 Correct 163 ms 388756 KB Output is correct
8 Correct 165 ms 388752 KB Output is correct
9 Correct 170 ms 388692 KB Output is correct
10 Correct 166 ms 388740 KB Output is correct
11 Correct 163 ms 388728 KB Output is correct
12 Correct 165 ms 388672 KB Output is correct
13 Correct 167 ms 388776 KB Output is correct
14 Correct 171 ms 388820 KB Output is correct
15 Correct 179 ms 388784 KB Output is correct
16 Correct 173 ms 388824 KB Output is correct
17 Correct 169 ms 388772 KB Output is correct
18 Correct 169 ms 388676 KB Output is correct
19 Correct 190 ms 389000 KB Output is correct
20 Correct 178 ms 388708 KB Output is correct
21 Correct 169 ms 388872 KB Output is correct
22 Correct 168 ms 388768 KB Output is correct
23 Correct 169 ms 388788 KB Output is correct
24 Correct 183 ms 388784 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 394700 KB Output is correct
2 Incorrect 867 ms 398852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 388656 KB Output is correct
2 Correct 165 ms 388840 KB Output is correct
3 Correct 170 ms 388660 KB Output is correct
4 Correct 166 ms 388680 KB Output is correct
5 Correct 168 ms 388684 KB Output is correct
6 Correct 182 ms 388696 KB Output is correct
7 Correct 163 ms 388756 KB Output is correct
8 Correct 165 ms 388752 KB Output is correct
9 Correct 170 ms 388692 KB Output is correct
10 Correct 166 ms 388740 KB Output is correct
11 Correct 163 ms 388728 KB Output is correct
12 Correct 165 ms 388672 KB Output is correct
13 Correct 167 ms 388776 KB Output is correct
14 Correct 171 ms 388820 KB Output is correct
15 Correct 179 ms 388784 KB Output is correct
16 Correct 173 ms 388824 KB Output is correct
17 Correct 169 ms 388772 KB Output is correct
18 Correct 169 ms 388676 KB Output is correct
19 Correct 190 ms 389000 KB Output is correct
20 Correct 178 ms 388708 KB Output is correct
21 Correct 169 ms 388872 KB Output is correct
22 Correct 168 ms 388768 KB Output is correct
23 Correct 169 ms 388788 KB Output is correct
24 Correct 183 ms 388784 KB Output is correct
25 Correct 614 ms 394700 KB Output is correct
26 Incorrect 867 ms 398852 KB Output isn't correct
27 Halted 0 ms 0 KB -