oj.uz

Submission #689554

# Submission time Handle Problem Language Result Execution time Memory
689554 2023-01-28T17:49:51 Z danikoynov Klasika (COCI20_klasika) C++14
110 / 110
 2345 ms 457804 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;
    set < int > in_times;
    trie *child[2];

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

const int maxn = 400100;

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;
}

void add(trie *root, int val, int pos)
{
    root -> in_times.insert(pos);
    if (root -> depth < 0)
        return;

    int bit = (1 << root -> depth), type = ((bit & val) > 0);
    if (root -> child[type] == NULL)
        root -> child[type] = new trie(root -> depth - 1);

    add(root -> child[type], val, pos);
}

bool in_interval(trie *cur, int left, int right)
{
    set < int > :: iterator it = cur -> in_times.lower_bound(left);
    if (it == cur -> in_times.end() ||
        *it > right)
            return false;
    return true;
}

int query(trie *root, int x, int left, int right)
{
    if (root -> depth < 0)
        return 0;

    int bit = (1 << root -> depth), type = (((bit & x) > 0) + 1) % 2;
    if (root -> child[type] == NULL ||
        !in_interval(root -> child[type], left, right))
            return query(root -> child[(type + 1) % 2], x, left, right);
    return query(root -> child[type], x, left, right) + bit;
}

trie *root = new trie(30);

void add_node(int ver)
{
    add(root, xor_depth[ver], tin[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);
    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(root, xor_depth[a], tin[b], tout[b]);
            cout << ans << endl;
        }
    }
}

int main()
{
    speed();
    solve();
    return 0;
}
/**

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25556 KB Output is correct
2 Correct 13 ms 25556 KB Output is correct
3 Correct 16 ms 25696 KB Output is correct
4 Correct 12 ms 25940 KB Output is correct
5 Correct 12 ms 25448 KB Output is correct
6 Correct 13 ms 25564 KB Output is correct
7 Correct 13 ms 25684 KB Output is correct
8 Correct 12 ms 25940 KB Output is correct
9 Correct 17 ms 25560 KB Output is correct
10 Correct 13 ms 25684 KB Output is correct
11 Correct 15 ms 25812 KB Output is correct
12 Correct 12 ms 25940 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25556 KB Output is correct
2 Correct 13 ms 25556 KB Output is correct
3 Correct 16 ms 25696 KB Output is correct
4 Correct 12 ms 25940 KB Output is correct
5 Correct 12 ms 25448 KB Output is correct
6 Correct 13 ms 25564 KB Output is correct
7 Correct 13 ms 25684 KB Output is correct
8 Correct 12 ms 25940 KB Output is correct
9 Correct 17 ms 25560 KB Output is correct
10 Correct 13 ms 25684 KB Output is correct
11 Correct 15 ms 25812 KB Output is correct
12 Correct 12 ms 25940 KB Output is correct
13 Correct 21 ms 26708 KB Output is correct
14 Correct 17 ms 28052 KB Output is correct
15 Correct 19 ms 29280 KB Output is correct
16 Correct 21 ms 30464 KB Output is correct
17 Correct 17 ms 26708 KB Output is correct
18 Correct 21 ms 27952 KB Output is correct
19 Correct 18 ms 29196 KB Output is correct
20 Correct 19 ms 30348 KB Output is correct
21 Correct 15 ms 26648 KB Output is correct
22 Correct 16 ms 27988 KB Output is correct
23 Correct 18 ms 29172 KB Output is correct
24 Correct 18 ms 30292 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 139900 KB Output is correct
2 Correct 1281 ms 247240 KB Output is correct
3 Correct 1769 ms 350192 KB Output is correct
4 Correct 2313 ms 453720 KB Output is correct
5 Correct 795 ms 138000 KB Output is correct
6 Correct 1287 ms 243208 KB Output is correct
7 Correct 1750 ms 344152 KB Output is correct
8 Correct 2171 ms 445212 KB Output is correct
9 Correct 847 ms 137640 KB Output is correct
10 Correct 1290 ms 244284 KB Output is correct
11 Correct 1675 ms 346600 KB Output is correct
12 Correct 2049 ms 447196 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25556 KB Output is correct
2 Correct 13 ms 25556 KB Output is correct
3 Correct 16 ms 25696 KB Output is correct
4 Correct 12 ms 25940 KB Output is correct
5 Correct 12 ms 25448 KB Output is correct
6 Correct 13 ms 25564 KB Output is correct
7 Correct 13 ms 25684 KB Output is correct
8 Correct 12 ms 25940 KB Output is correct
9 Correct 17 ms 25560 KB Output is correct
10 Correct 13 ms 25684 KB Output is correct
11 Correct 15 ms 25812 KB Output is correct
12 Correct 12 ms 25940 KB Output is correct
13 Correct 21 ms 26708 KB Output is correct
14 Correct 17 ms 28052 KB Output is correct
15 Correct 19 ms 29280 KB Output is correct
16 Correct 21 ms 30464 KB Output is correct
17 Correct 17 ms 26708 KB Output is correct
18 Correct 21 ms 27952 KB Output is correct
19 Correct 18 ms 29196 KB Output is correct
20 Correct 19 ms 30348 KB Output is correct
21 Correct 15 ms 26648 KB Output is correct
22 Correct 16 ms 27988 KB Output is correct
23 Correct 18 ms 29172 KB Output is correct
24 Correct 18 ms 30292 KB Output is correct
25 Correct 759 ms 139900 KB Output is correct
26 Correct 1281 ms 247240 KB Output is correct
27 Correct 1769 ms 350192 KB Output is correct
28 Correct 2313 ms 453720 KB Output is correct
29 Correct 795 ms 138000 KB Output is correct
30 Correct 1287 ms 243208 KB Output is correct
31 Correct 1750 ms 344152 KB Output is correct
32 Correct 2171 ms 445212 KB Output is correct
33 Correct 847 ms 137640 KB Output is correct
34 Correct 1290 ms 244284 KB Output is correct
35 Correct 1675 ms 346600 KB Output is correct
36 Correct 2049 ms 447196 KB Output is correct
37 Correct 1241 ms 140600 KB Output is correct
38 Correct 1697 ms 250436 KB Output is correct
39 Correct 2083 ms 356300 KB Output is correct
40 Correct 2142 ms 457804 KB Output is correct
41 Correct 1234 ms 141156 KB Output is correct
42 Correct 1709 ms 246092 KB Output is correct
43 Correct 2033 ms 347480 KB Output is correct
44 Correct 2345 ms 447960 KB Output is correct
45 Correct 1304 ms 140872 KB Output is correct
46 Correct 1772 ms 247192 KB Output is correct
47 Correct 2094 ms 348696 KB Output is correct
48 Correct 2208 ms 450632 KB Output is correct