제출 #1263673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263673		anarch_y	Klasika (COCI20_klasika)	C++20	110 / 110	2400 ms	300884 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct Trie{
    vector<vector<int>> trie;
    int num;

    void init(int k){
        trie.resize(30*k, vector<int>(2));
        num = 0;
    }
 
    void insert(int x){
        int cur = 0;
        for(int i=30; i>=0; i--){
            bool c = x & (1<<i);
            if(trie[cur][c] == 0){
                trie[cur][c] = ++num;
            }
            cur = trie[cur][c];
        }
    }
 
    int max_xor(int x){
        int cur = 0;
        int res = 0;
        for(int i=30; i>=0; i--){
            bool c = x & (1<<i);
            if(trie[cur][1-c]){
                res += (1<<i);
                cur = trie[cur][1-c];
            }
            else{
                cur = trie[cur][c];
            }
        }
        return res;
    }
};

const int maxn = 200001;
vector<int> adj[maxn];
int B[maxn], sub[maxn], id[maxn];
vector<int> tour;

void dfs(int s, int p){
    sub[s] = 1;
    tour.pb(s);
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        sub[s] += sub[u];
    }
}

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

    int q; cin >> q;
    int n = 1;
    vector<vector<int>> qry;
    while(q--){
        string s; cin >> s;
        if(s == "Add"){
            int x, y; cin >> x >> y;
            n++;
            adj[x].pb(n); adj[n].pb(x);
            B[n] = (B[x]^y);
            qry.pb({0, n});
        }
        else{
            int a, b; cin >> a >> b;
            qry.pb({1, a, b});
        }
    }
    dfs(1, 0);
    vector<int> A(n);
    for(int i=0; i<n; i++){
        id[tour[i]] = i;
        A[i] = B[tour[i]];
    }
    const int k = 5000;
    int m = (n-1)/k;
    Trie T[m+1];
    for(int i=0; i<=m; i++){
        T[i].init(k);
    }
    vector<int> v(n, -1);
    v[0] = 0;
    T[0].insert(0);
    auto query = [&](int l, int r, int z){
        int x = l/k, y = r/k;
        int ans = 0;
        if(x+1 <= y-1){
            for(int i=x+1; i<=y-1; i++){
                if(T[i].num != 0){
                    ans = max(ans, T[i].max_xor(z));
                }
            }
            for(int i=l; i<(x+1)*k; i++){
                if(v[i] != -1){
                    ans = max(ans, (z^v[i]));
                }
            }
            for(int i=y*k; i<=r; i++){
                if(v[i] != -1){
                    ans = max(ans, (z^v[i]));
                }
            }
        }
        else{
            for(int i=l; i<=r; i++){
                if(v[i] != -1){
                    ans = max(ans, (z^v[i]));
                }
            }
        }
        return ans;
    };
    for(auto w: qry){
        if(w[0] == 0){
            int x = w[1];
            v[id[x]] = A[id[x]];
            int i = id[x]/k;
            T[i].insert(A[id[x]]);
        }
        else{
            int a = w[1], b = w[2];
            int ans = query(id[b], id[b]+sub[b]-1, B[a]);
            cout << ans << "\n";
        }
    }
}

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