oj.uz

Submission #689538

# Submission time Handle Problem Language Result Execution time Memory
689538 2023-01-28T17:28:37 Z danikoynov Klasika (COCI20_klasika) C++14
66 / 110
 450 ms 406292 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 (q > 2000)
        return;
    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 177 ms 388752 KB Output is correct
2 Correct 183 ms 388692 KB Output is correct
3 Correct 171 ms 388672 KB Output is correct
4 Correct 173 ms 388672 KB Output is correct
5 Correct 200 ms 388692 KB Output is correct
6 Correct 174 ms 388676 KB Output is correct
7 Correct 188 ms 388692 KB Output is correct
8 Correct 176 ms 388840 KB Output is correct
9 Correct 177 ms 388644 KB Output is correct
10 Correct 201 ms 388756 KB Output is correct
11 Correct 178 ms 388768 KB Output is correct
12 Correct 192 ms 388688 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 388752 KB Output is correct
2 Correct 183 ms 388692 KB Output is correct
3 Correct 171 ms 388672 KB Output is correct
4 Correct 173 ms 388672 KB Output is correct
5 Correct 200 ms 388692 KB Output is correct
6 Correct 174 ms 388676 KB Output is correct
7 Correct 188 ms 388692 KB Output is correct
8 Correct 176 ms 388840 KB Output is correct
9 Correct 177 ms 388644 KB Output is correct
10 Correct 201 ms 388756 KB Output is correct
11 Correct 178 ms 388768 KB Output is correct
12 Correct 192 ms 388688 KB Output is correct
13 Correct 194 ms 388796 KB Output is correct
14 Correct 179 ms 388776 KB Output is correct
15 Correct 231 ms 388796 KB Output is correct
16 Correct 244 ms 388888 KB Output is correct
17 Correct 190 ms 388700 KB Output is correct
18 Correct 195 ms 388780 KB Output is correct
19 Correct 182 ms 388820 KB Output is correct
20 Correct 195 ms 388844 KB Output is correct
21 Correct 174 ms 388736 KB Output is correct
22 Correct 175 ms 388764 KB Output is correct
23 Correct 171 ms 388740 KB Output is correct
24 Correct 171 ms 388736 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 394844 KB Output is correct
2 Correct 398 ms 398556 KB Output is correct
3 Correct 423 ms 401840 KB Output is correct
4 Correct 431 ms 406292 KB Output is correct
5 Correct 387 ms 392396 KB Output is correct
6 Correct 422 ms 393796 KB Output is correct
7 Correct 415 ms 394760 KB Output is correct
8 Correct 420 ms 396648 KB Output is correct
9 Correct 407 ms 392712 KB Output is correct
10 Correct 398 ms 394652 KB Output is correct
11 Correct 406 ms 395956 KB Output is correct
12 Correct 450 ms 398312 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 388752 KB Output is correct
2 Correct 183 ms 388692 KB Output is correct
3 Correct 171 ms 388672 KB Output is correct
4 Correct 173 ms 388672 KB Output is correct
5 Correct 200 ms 388692 KB Output is correct
6 Correct 174 ms 388676 KB Output is correct
7 Correct 188 ms 388692 KB Output is correct
8 Correct 176 ms 388840 KB Output is correct
9 Correct 177 ms 388644 KB Output is correct
10 Correct 201 ms 388756 KB Output is correct
11 Correct 178 ms 388768 KB Output is correct
12 Correct 192 ms 388688 KB Output is correct
13 Correct 194 ms 388796 KB Output is correct
14 Correct 179 ms 388776 KB Output is correct
15 Correct 231 ms 388796 KB Output is correct
16 Correct 244 ms 388888 KB Output is correct
17 Correct 190 ms 388700 KB Output is correct
18 Correct 195 ms 388780 KB Output is correct
19 Correct 182 ms 388820 KB Output is correct
20 Correct 195 ms 388844 KB Output is correct
21 Correct 174 ms 388736 KB Output is correct
22 Correct 175 ms 388764 KB Output is correct
23 Correct 171 ms 388740 KB Output is correct
24 Correct 171 ms 388736 KB Output is correct
25 Correct 400 ms 394844 KB Output is correct
26 Correct 398 ms 398556 KB Output is correct
27 Correct 423 ms 401840 KB Output is correct
28 Correct 431 ms 406292 KB Output is correct
29 Correct 387 ms 392396 KB Output is correct
30 Correct 422 ms 393796 KB Output is correct
31 Correct 415 ms 394760 KB Output is correct
32 Correct 420 ms 396648 KB Output is correct
33 Correct 407 ms 392712 KB Output is correct
34 Correct 398 ms 394652 KB Output is correct
35 Correct 406 ms 395956 KB Output is correct
36 Correct 450 ms 398312 KB Output is correct
37 Incorrect 365 ms 393272 KB Output isn't correct
38 Halted 0 ms 0 KB -