oj.uz

Submission #689529

# Submission time Handle Problem Language Result Execution time Memory
689529 2023-01-28T17:18:49 Z danikoynov Klasika (COCI20_klasika) C++14
66 / 110
 374 ms 111480 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 (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)
{
    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 13268 KB Output is correct
3 Correct 8 ms 13652 KB Output is correct
4 Correct 8 ms 13948 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 9 ms 13268 KB Output is correct
7 Correct 8 ms 13524 KB Output is correct
8 Correct 9 ms 14036 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13396 KB Output is correct
11 Correct 7 ms 13652 KB Output is correct
12 Correct 8 ms 14028 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 13268 KB Output is correct
3 Correct 8 ms 13652 KB Output is correct
4 Correct 8 ms 13948 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 9 ms 13268 KB Output is correct
7 Correct 8 ms 13524 KB Output is correct
8 Correct 9 ms 14036 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13396 KB Output is correct
11 Correct 7 ms 13652 KB Output is correct
12 Correct 8 ms 14028 KB Output is correct
13 Correct 14 ms 16340 KB Output is correct
14 Correct 19 ms 20276 KB Output is correct
15 Correct 22 ms 24412 KB Output is correct
16 Correct 27 ms 28224 KB Output is correct
17 Correct 15 ms 16212 KB Output is correct
18 Correct 19 ms 20052 KB Output is correct
19 Correct 23 ms 24180 KB Output is correct
20 Correct 28 ms 28080 KB Output is correct
21 Correct 15 ms 16212 KB Output is correct
22 Correct 17 ms 20052 KB Output is correct
23 Correct 21 ms 24148 KB Output is correct
24 Correct 25 ms 28056 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 41504 KB Output is correct
2 Correct 293 ms 65868 KB Output is correct
3 Correct 316 ms 87728 KB Output is correct
4 Correct 349 ms 111480 KB Output is correct
5 Correct 256 ms 39220 KB Output is correct
6 Correct 304 ms 61136 KB Output is correct
7 Correct 374 ms 80788 KB Output is correct
8 Correct 350 ms 102164 KB Output is correct
9 Correct 256 ms 39524 KB Output is correct
10 Correct 286 ms 61956 KB Output is correct
11 Correct 327 ms 82288 KB Output is correct
12 Correct 340 ms 103876 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13140 KB Output is correct
2 Correct 7 ms 13268 KB Output is correct
3 Correct 8 ms 13652 KB Output is correct
4 Correct 8 ms 13948 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 9 ms 13268 KB Output is correct
7 Correct 8 ms 13524 KB Output is correct
8 Correct 9 ms 14036 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13396 KB Output is correct
11 Correct 7 ms 13652 KB Output is correct
12 Correct 8 ms 14028 KB Output is correct
13 Correct 14 ms 16340 KB Output is correct
14 Correct 19 ms 20276 KB Output is correct
15 Correct 22 ms 24412 KB Output is correct
16 Correct 27 ms 28224 KB Output is correct
17 Correct 15 ms 16212 KB Output is correct
18 Correct 19 ms 20052 KB Output is correct
19 Correct 23 ms 24180 KB Output is correct
20 Correct 28 ms 28080 KB Output is correct
21 Correct 15 ms 16212 KB Output is correct
22 Correct 17 ms 20052 KB Output is correct
23 Correct 21 ms 24148 KB Output is correct
24 Correct 25 ms 28056 KB Output is correct
25 Correct 252 ms 41504 KB Output is correct
26 Correct 293 ms 65868 KB Output is correct
27 Correct 316 ms 87728 KB Output is correct
28 Correct 349 ms 111480 KB Output is correct
29 Correct 256 ms 39220 KB Output is correct
30 Correct 304 ms 61136 KB Output is correct
31 Correct 374 ms 80788 KB Output is correct
32 Correct 350 ms 102164 KB Output is correct
33 Correct 256 ms 39524 KB Output is correct
34 Correct 286 ms 61956 KB Output is correct
35 Correct 327 ms 82288 KB Output is correct
36 Correct 340 ms 103876 KB Output is correct
37 Incorrect 237 ms 43548 KB Output isn't correct
38 Halted 0 ms 0 KB -