oj.uz

Submission #689528

# Submission time Handle Problem Language Result Execution time Memory
689528 2023-01-28T17:18:15 Z danikoynov Klasika (COCI20_klasika) C++14
33 / 110
 363 ms 115192 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);
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 41496 KB Output is correct
2 Correct 278 ms 69116 KB Output is correct
3 Correct 310 ms 91096 KB Output is correct
4 Correct 345 ms 115192 KB Output is correct
5 Correct 258 ms 41996 KB Output is correct
6 Correct 302 ms 64240 KB Output is correct
7 Correct 324 ms 84208 KB Output is correct
8 Correct 363 ms 105744 KB Output is correct
9 Correct 245 ms 42280 KB Output is correct
10 Correct 285 ms 65096 KB Output is correct
11 Correct 320 ms 85624 KB Output is correct
12 Correct 349 ms 107648 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12884 KB Output isn't correct
2 Halted 0 ms 0 KB -