제출 #1163715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163715		LmaoLmao	Klasika (COCI20_klasika)	C++17	33 / 110	1415 ms	559104 KiB

klasika

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

int d[200005];
int val[6000001];
vector<int> adj[200005];
int trie[6000001][2];
multiset<int> a[6000001];
int timer = 0;
int kien=1;
int st[200005],ed[200005];
int t = 0;
void elt(int u){
    st[u] = ++t;
    for(int v : adj[u]){
        elt(v);
    }
    ed[u] = t;
}
int get(int x,int l,int r){
    int u = 0;
    for(int i = 30;i >= 0;i--){
       int v = (d[x] >> i)&1;
       if(!v){ 
          auto it = a[trie[u][1]].lower_bound(l);
          if(it!=a[trie[u][1]].end() && *it <= r){
              u = trie[u][1];
          }else{
              u = trie[u][0];
          }
    
       }else{
          auto it = a[trie[u][0]].lower_bound(l);
            if(it!=a[trie[u][0]].end() &&*it <= r){
              u = trie[u][0];
          }else{
              u = trie[u][1];
          }
       }
    }
    return val[u] ^ d[x];
}
void add(int x){
    int u = 0;
    for(int i = 30;i >= 0;i--){
        int v = (d[x] >> i) & 1;
        if(!trie[u][v]) trie[u][v] = ++timer;
        u = trie[u][v];
        a[u].insert(st[x]);
    }
    //cout << timer << ' ' << val[u] << endl;
    val[u] = d[x];
    
}
int query[200005][3];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int q; cin >> q;
    for(int i = 1;i <= q;i++){
        string s; cin >> s;
        int x, y; cin >> x>> y;
        query[i][1] = x;
        query[i][2] = y;
        if (s == "Add"){
            query[i][0] = 0;
            d[++kien]= d[x] ^ y;
            adj[x].push_back(kien);
        }else{
            query[i][0] = 1;
        }
    }
    elt(1);
    kien = 1;
    add(1);
    for(int i = 1;i <= q;i++){
        if(!query[i][0]){
            add(++kien);
        }else{
            cout << get(query[i][1],st[query[i][2]],ed[query[i][2]]) << "\n";
        }
    }
    return 0;
}

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