제출 #1306413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306413		nguyenkhangninh99	Klasika (COCI20_klasika)	C++20	110 / 110	380 ms	127740 KiB

klasika

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 2e5 + 5, lg = 31;
int tin[maxn], out[maxn], dist[maxn], timedfs;
vector<int> stp[4 * maxn], stq[4 * maxn];
vector<pair<int, int>> g[maxn];
int trie[maxn * lg][2], hist[maxn * lg], top/*ptr for hist*/, triesz;
int res[maxn], type[maxn];
struct pipi{
    int a, b, t, id;
} qry[maxn];
void dfs(int u, int p){
    tin[u] = ++timedfs;
    for(pair<int, int> x: g[u]){
        int v = x.first, w = x.second;
        dist[v] = dist[u] ^ w;
        dfs(v, u);
    }
    out[u] = timedfs;
}
void addp(int id, int l, int r, int p, int v){
    stp[id].push_back(v);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(p <= mid) addp(id * 2, l, mid, p, v);
    else addp(id * 2 + 1, mid + 1, r, p, v);
}
void addq(int id, int l, int r, int u, int v, int val){
    if(u <= l && r <= v){
        stq[id].push_back(val);
        return;
    }
    int mid = (l + r) / 2;
    if(u <= mid) addq(id * 2, l, mid, u, v, val);
    if(mid < v) addq(id * 2 + 1, mid + 1, r, u, v, val);
}
void insert(int val){
    int u = 0;
    for(int bit = 30; bit >= 0; bit--){
        int b = (val >> bit) & 1;
        if(!trie[u][b]){
            trie[u][b] = ++triesz;
            hist[++top] = trie[u][b];
        }
        u = trie[u][b];
    }
}
int get(int val){
    int u = 0, ans = 0;
    for(int bit = 30; bit >= 0; bit--){
        int b = (val >> bit) & 1;
        if(trie[u][!b]){
            ans |= (1LL << bit);
            u = trie[u][!b];
        }else u = trie[u][b];
    }
    return ans;
}

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

    int curq = 0, n = 1;
    int q; cin >> q;
    for(int i = 1; i <= q; i++){
        string s; cin >> s;
        if(s == "Add"){
            int v, w; cin >> v >> w;
            g[v].push_back({++n, w});
            type[i] = 1;
        }else{
            int a, b; cin >> a >> b;
            qry[curq++] = {a, b, n, i};
            type[i] = 2;
        }
    }

    dfs(1, 0);
    for(int i = 1; i <= n; i++) addp(1, 1, n, tin[i], i);
    for(int i = 0; i < curq; i++) addq(1, 1, n, tin[qry[i].b], out[qry[i].b], i);

    for(int i = 1; i < 4 * maxn; i++){
        int ptr = 0;
        for(int x: stq[i]){
            while(ptr < stp[i].size() && stp[i][ptr] <= qry[x].t) insert(dist[stp[i][ptr++]]);
            res[qry[x].id] = max(res[qry[x].id], get(dist[qry[x].a]));
        }
        while(top){
            int u = hist[top--];
            trie[u][0] = trie[u][1] = 0;
        }
        trie[0][0] = trie[0][1] = triesz = 0;
    }
    for(int i = 0; i < curq; i++) cout << res[qry[i].id] << "\n";
}

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