제출 #1368819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368819		tranvinhhuy2010	Klasika (COCI20_klasika)	C++20	33 / 110	1296 ms	584616 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5 + 5;
int q, timer, d[nmax], in[nmax], out[nmax], ch[nmax*32][2], num;
vector <pair <int, int>> g[nmax];
set <int> adu[nmax*32];
vector <tuple <string, int, int>> qs;

void dfs(int u, int p) {
    in[u] = ++timer;
    for (auto [v, w] : g[u]) {
        d[v] = d[u] ^ w;
        dfs(v, u);
    }

    out[u] = timer;
}

int bit(int x, int i) {
    return x >> i & 1;
}

void add_node(int u) {
    int cur = 1;
    adu[cur].insert(in[u]);

    for (int i=30; i>=0; i--) {
        int b = bit(d[u], i);
        if (!ch[cur][b]) ch[cur][b] = ++num;
        cur = ch[cur][b];
        adu[cur].insert(in[u]);
    }
}

int get(int a, int b) {
    int cur = 1, ans = 0;
    for (int i=30; i>=0; i--) {
        int val = bit(d[a], i), opla = 1 - val;

        if (ch[cur][opla]>0) {
            int nxt = ch[cur][opla];
            auto it = adu[nxt].lower_bound(in[b]);

            if (it!=adu[nxt].end() && *it<=out[b]) {
                ans += (1 << i);
                cur = nxt;
                continue;
            }
        }

        cur = ch[cur][val];
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> q;

    int cnt = 1;
    for (int i=0; i<q; i++) {
        string s; int x, y;
        cin >> s >> x >> y;
        if (s=="Add") {
            cnt++;
            g[x].push_back({cnt, y});
        }
        qs.push_back({s, x, y});
    }

    d[1] = timer = 0;
    dfs(1, 0);

    num = 1;
    add_node(1);

    cnt = 1;
    for (auto& [s, x, y] : qs) {
        if (s=="Add") add_node(++cnt);
        else cout << get(x, y) << '\n';
    }

    return 0;
}

• 서브태스크 1: 11 / 11
• 서브태스크 2: 22 / 22
• 서브태스크 3: 0 / 33
• 서브태스크 4: 0 / 44