oj.uz

Submission #689534

# Submission time Handle Problem Language Result Execution time Memory
689534 2023-01-28T17:26:53 Z danikoynov Klasika (COCI20_klasika) C++14
33 / 110
 860 ms 398876 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 164 ms 388752 KB Output is correct
2 Correct 167 ms 388644 KB Output is correct
3 Correct 165 ms 388648 KB Output is correct
4 Correct 167 ms 388816 KB Output is correct
5 Correct 170 ms 388680 KB Output is correct
6 Correct 165 ms 388636 KB Output is correct
7 Correct 169 ms 388708 KB Output is correct
8 Correct 186 ms 388652 KB Output is correct
9 Correct 166 ms 388684 KB Output is correct
10 Correct 176 ms 388676 KB Output is correct
11 Correct 173 ms 388684 KB Output is correct
12 Correct 165 ms 388752 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 388752 KB Output is correct
2 Correct 167 ms 388644 KB Output is correct
3 Correct 165 ms 388648 KB Output is correct
4 Correct 167 ms 388816 KB Output is correct
5 Correct 170 ms 388680 KB Output is correct
6 Correct 165 ms 388636 KB Output is correct
7 Correct 169 ms 388708 KB Output is correct
8 Correct 186 ms 388652 KB Output is correct
9 Correct 166 ms 388684 KB Output is correct
10 Correct 176 ms 388676 KB Output is correct
11 Correct 173 ms 388684 KB Output is correct
12 Correct 165 ms 388752 KB Output is correct
13 Correct 178 ms 388720 KB Output is correct
14 Correct 183 ms 388732 KB Output is correct
15 Correct 179 ms 388812 KB Output is correct
16 Correct 169 ms 388800 KB Output is correct
17 Correct 175 ms 388676 KB Output is correct
18 Correct 180 ms 388720 KB Output is correct
19 Correct 176 ms 388820 KB Output is correct
20 Correct 176 ms 388732 KB Output is correct
21 Correct 208 ms 388704 KB Output is correct
22 Correct 179 ms 388688 KB Output is correct
23 Correct 171 ms 388812 KB Output is correct
24 Correct 172 ms 388808 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 394780 KB Output is correct
2 Incorrect 860 ms 398876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 388752 KB Output is correct
2 Correct 167 ms 388644 KB Output is correct
3 Correct 165 ms 388648 KB Output is correct
4 Correct 167 ms 388816 KB Output is correct
5 Correct 170 ms 388680 KB Output is correct
6 Correct 165 ms 388636 KB Output is correct
7 Correct 169 ms 388708 KB Output is correct
8 Correct 186 ms 388652 KB Output is correct
9 Correct 166 ms 388684 KB Output is correct
10 Correct 176 ms 388676 KB Output is correct
11 Correct 173 ms 388684 KB Output is correct
12 Correct 165 ms 388752 KB Output is correct
13 Correct 178 ms 388720 KB Output is correct
14 Correct 183 ms 388732 KB Output is correct
15 Correct 179 ms 388812 KB Output is correct
16 Correct 169 ms 388800 KB Output is correct
17 Correct 175 ms 388676 KB Output is correct
18 Correct 180 ms 388720 KB Output is correct
19 Correct 176 ms 388820 KB Output is correct
20 Correct 176 ms 388732 KB Output is correct
21 Correct 208 ms 388704 KB Output is correct
22 Correct 179 ms 388688 KB Output is correct
23 Correct 171 ms 388812 KB Output is correct
24 Correct 172 ms 388808 KB Output is correct
25 Correct 586 ms 394780 KB Output is correct
26 Incorrect 860 ms 398876 KB Output isn't correct
27 Halted 0 ms 0 KB -