oj.uz

답안 #689543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689543 2023-01-28T17:31:22 Z danikoynov Klasika (COCI20_klasika) C++14
33 / 110
 978 ms 508116 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 = 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;
}

trie tree[2 * maxn * 50];
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)
    {
        if (last_used + 1 == 2 * maxn * 50)
        {
            exit(0);
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 495120 KB Output is correct
2 Correct 210 ms 495120 KB Output is correct
3 Correct 221 ms 495212 KB Output is correct
4 Correct 212 ms 495100 KB Output is correct
5 Correct 218 ms 495156 KB Output is correct
6 Correct 218 ms 495060 KB Output is correct
7 Correct 215 ms 495180 KB Output is correct
8 Correct 207 ms 495056 KB Output is correct
9 Correct 212 ms 495104 KB Output is correct
10 Correct 211 ms 495124 KB Output is correct
11 Correct 209 ms 495064 KB Output is correct
12 Correct 212 ms 495124 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 495120 KB Output is correct
2 Correct 210 ms 495120 KB Output is correct
3 Correct 221 ms 495212 KB Output is correct
4 Correct 212 ms 495100 KB Output is correct
5 Correct 218 ms 495156 KB Output is correct
6 Correct 218 ms 495060 KB Output is correct
7 Correct 215 ms 495180 KB Output is correct
8 Correct 207 ms 495056 KB Output is correct
9 Correct 212 ms 495104 KB Output is correct
10 Correct 211 ms 495124 KB Output is correct
11 Correct 209 ms 495064 KB Output is correct
12 Correct 212 ms 495124 KB Output is correct
13 Correct 213 ms 495192 KB Output is correct
14 Correct 230 ms 495168 KB Output is correct
15 Correct 223 ms 495200 KB Output is correct
16 Correct 218 ms 495324 KB Output is correct
17 Correct 213 ms 495080 KB Output is correct
18 Correct 220 ms 495180 KB Output is correct
19 Correct 214 ms 495128 KB Output is correct
20 Correct 223 ms 495188 KB Output is correct
21 Correct 214 ms 495180 KB Output is correct
22 Correct 224 ms 495264 KB Output is correct
23 Correct 216 ms 495164 KB Output is correct
24 Correct 228 ms 495240 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 501132 KB Output is correct
2 Correct 889 ms 505096 KB Output is correct
3 Incorrect 978 ms 508116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 495120 KB Output is correct
2 Correct 210 ms 495120 KB Output is correct
3 Correct 221 ms 495212 KB Output is correct
4 Correct 212 ms 495100 KB Output is correct
5 Correct 218 ms 495156 KB Output is correct
6 Correct 218 ms 495060 KB Output is correct
7 Correct 215 ms 495180 KB Output is correct
8 Correct 207 ms 495056 KB Output is correct
9 Correct 212 ms 495104 KB Output is correct
10 Correct 211 ms 495124 KB Output is correct
11 Correct 209 ms 495064 KB Output is correct
12 Correct 212 ms 495124 KB Output is correct
13 Correct 213 ms 495192 KB Output is correct
14 Correct 230 ms 495168 KB Output is correct
15 Correct 223 ms 495200 KB Output is correct
16 Correct 218 ms 495324 KB Output is correct
17 Correct 213 ms 495080 KB Output is correct
18 Correct 220 ms 495180 KB Output is correct
19 Correct 214 ms 495128 KB Output is correct
20 Correct 223 ms 495188 KB Output is correct
21 Correct 214 ms 495180 KB Output is correct
22 Correct 224 ms 495264 KB Output is correct
23 Correct 216 ms 495164 KB Output is correct
24 Correct 228 ms 495240 KB Output is correct
25 Correct 628 ms 501132 KB Output is correct
26 Correct 889 ms 505096 KB Output is correct
27 Incorrect 978 ms 508116 KB Output isn't correct
28 Halted 0 ms 0 KB -