Submission #212130

#	Time	Username	Problem	Language	Result	Execution time	Memory
212130		NONAME	Klasika (COCI20_klasika)	C++17	110 / 110	441 ms	70648 KiB

klasika

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 31;
const int M = PW * N;
const int K = 10010;
const int oo = 2e9;
vector<pii> qr[N];
vector<int> g[N];
string qur;
int ans[N], pr[N], xr[N], koli, siz[N], lst = 1, net[M][2], kol[M], tim[N], mn[M], n, q;
bool typ[N];
 
void build_sz(int v){
    siz[v] = 1;
    
    for (int u : g[v]){
        build_sz(u);
        siz[v] += siz[u];
    }
}

void insert(int vl, int tm){
    int st = 1;
    
    for (int po = PW - 1; po >= 0; po--){
        int bt = bool(vl & (1 << po));
        
        if (net[st][bt] == 0){
            net[st][bt] = ++lst;
            kol[lst] = 0;
            mn[lst] = tm;
        }
        
        st = net[st][bt];
        mn[st] = min(mn[st], tm);
        kol[st]++;
    }
}

void CLEAR(){
    for (int i = 1; i <= lst; i++){
        net[i][0] = net[i][1] = 0;
    }
    lst = 1;
}

void insert_dfs(int v){
    insert(xr[v], tim[v]);
    
    for (int u : g[v])
        insert_dfs(u);
}

int answer(int mx_tim, int vl){
    int res = 0, st = 1;
    
    for (int po = PW - 1; po >= 0; po--){
        int bt = bool(vl & (1 << po));
        
        if (net[st][bt ^ 1] != 0 && mn[net[st][bt ^ 1]] <= mx_tim){
            res += (1 << po);
            st = net[st][bt ^ 1];
        } else st = net[st][bt];
    }
    
    return res;
}

void dfs(int v, bool mrk){
    int mx = -1, nom = -1;
    
    for (int u : g[v])
        if (siz[u] > mx){
            mx = siz[u];
            nom = u;
        }
        
    if (mx < 0){
        for (pii cr : qr[v])
            ans[cr.ft] = xr[cr.sd] ^ xr[v];
        
        if (mrk){
            insert(xr[v], tim[v]);
        } 
    } else {
        
        for (int u : g[v])
            if (u != nom)
                dfs(u, 0);
        
        dfs(nom, 1);
        
        insert(xr[v], tim[v]);
        
        for (int u : g[v])
            if (u != nom)
                insert_dfs(u);
            
        for (pii cr : qr[v])
            ans[cr.ft] = answer(cr.ft, xr[cr.sd]);
    }
    
    if (!mrk)
        CLEAR();
}
 
int main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);

    cin >> q;
    
    tim[0] = -1;
    pr[0] = -1;
    xr[0] = 0;
    koli = 1;
    
    for (int i = 0; i < q; i++){
        cin >> qur;
        
        if (qur[0] == 'Q'){
            typ[i] = 1;
            int x, y; cin >> x >> y;
            x--; y--;
            
            qr[y].PB(MP(i, x));
        } else {
            
            int x, y; cin >> x >> y;
            x--;
            
            tim[koli] = i;
            pr[koli] = x;
            xr[koli] = xr[x] ^ y;
            g[x].PB(koli);
            koli++;
        }
    }
    
    build_sz(0);
    
    dfs(0, 0);
    
    for (int i = 0; i < q; i++)
        if (typ[i])
            cout << ans[i] << '\n';
  
    return 0;
}

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