Submission #1117563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117563		LonlyR	Klasika (COCI20_klasika)	C++17	110 / 110	2410 ms	515128 KiB

klasika

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e5 + 5;
int q, n = 1, cnt;
int in[maxn], out[maxn], val[maxn];
vector<pair<int,int>> adj[maxn];
tuple<int,int,int> query[maxn];

struct node{
    int c[2];
    set<int> s;
    node()
    {
        c[0] = c[1] = 0;
        s.clear();
    }
};

vector<node> T(1);

void add(int x, int y)
{
    for (int i = 30, cur = 0; i >= 0; i--)
    {
        int nxt = x >> i & 1;
        if (T[cur].c[nxt] == 0) T[cur].c[nxt] = T.size(), T.emplace_back();
        cur = T[cur].c[nxt];
        T[cur].s.emplace(y);
    }
}

bool check(set<int> &x, int y)
{
    auto it = x.lower_bound(in[y]);
    return it != x.end() && (*it) <= out[y];
}

int qry(int X, int y, int cur = 0, int bit = 30)
{
    if (bit == -1) return 0;
    int nxt = X >> bit & 1;
    if (T[cur].c[nxt ^ 1] && check(T[T[cur].c[nxt ^ 1]].s, y))
        return (1ll << bit) + qry(X, y, T[cur].c[nxt ^ 1], bit - 1);
    return qry(X, y, T[cur].c[nxt], bit - 1);
}

void dfs(int x = 1, int p = 0)
{
    in[x] = ++cnt;
    for (auto [i, w] : adj[x]) if (i != p)
        val[i] = val[x] ^ w,
        dfs(i, x);
    out[x] = cnt;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        string s; int x, y;
        cin >> s >> x >> y;
        if (s[0] == 'A')
            adj[x].emplace_back(++n, y), query[i] = {1, n, y};
        else query[i] = {0, x, y};
    }
    dfs();
    add(0, 1);
    for (int i = 1; i <= q; i++)
    {
        auto [type, x, y] = query[i];
        if (type == 1)
            add(val[x], in[x]);
        else cout << qry(val[x], y) << "\n";
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44