| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1312568 | iamsazidh | Klasika (COCI20_klasika) | C++20 | 0 ms | 0 KiB |
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define file(); freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#define debug(...)
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__);
template <class X, class Y>
ostream& operator<<(ostream& os, const pair<X, Y>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, const Container& x) {
int i = 0, n = distance(x.begin(), x.end());
os << "{ ";
for (const auto& y : x)
os << y << (++i < n ? ", " : "");
return os << " }";
}
template <typename... Args>
void _debug(const char* names, Args&&... args) {
string_view s(names);
cerr << "{ ";
size_t i = 0, cnt = 0, n = sizeof...(args);
auto next = [&]() {
while (i < s.size() && (s[i] == ' ' || s[i] == ',')) ++i;
size_t st = i;
while (i < s.size() && s[i] != ',') ++i;
return s.substr(st, i - st);
};
((cerr << next() << ": " << args << (++cnt < n ? ", " : "")), ...);
cerr << " }" << '\n';
}
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
const double EPS = 1e-6;
const int MAXN = 200000+100;
const int logN = 31;
class Trie{
public:
struct node{
bool val;
vi child = vi(2, -1);
// set<int> st;
};
vector<node> arr;
int timer = 1;
Trie() {
arr.resize(MAXN*logN);
arr.back().st.insert(inf);
}
void add(int x, int val){ // node no, value
int now = 0;
arr[now].st.insert(x);
for(int i = logN; i >= 0; i--){
bool v = (val>>i) &1;
if(arr[now].child[v]==-1){
arr[timer].val = v;
arr[timer].st.insert(inf);
arr[now].child[v] = timer++;
}
now = arr[now].child[v];
arr[now].st.insert(x);
}
}
void remove(int x, int val){
int now = 0;
arr[now].st.erase(x);
for(int i = logN; i >= 0; i--){
bool v = (val>>i) &1;
now = arr[now].child[v];
arr[now].st.erase(x);
}
}
int query(int val, int l, int r){
int now = 0;
int ans = 0;
for(int i = logN; i >= 0; i--){
bool need = !((val>>i) &1);
int got = need;
if(arr[now].child[need]==-1 || (*arr[arr[now].child[need]].st.lower_bound(l))>r) got = !need;
if(got==need) ans += 1<<i;
now = arr[now].child[got];
}
return ans;
}
void printAll(){
int idx = 0;
for(auto x: arr){
deb(idx++)
cerr << x.val << spc << x.child[0] << spc << x.child[1] << endl;
debug(x.st);
}
}
};
int ttimer = 0;
Trie* trie;
void dfs(vii &adj, int i, vi &xr, vector<pii> &ett){
ett[i].ff = ++ttimer;
trie->add(ttimer, xr[i]);
for(auto x: adj[i]) dfs(adj, x, xr, ett);
ett[i].ss = ttimer;
return;
}
bool solve(){
int q; cin >> q;
vii adj(MAXN);
vi xr(MAXN, 0);
trie = new Trie();
int timer = 2;
vector<pair<int, pii>> query;
int cntQ = 0;
int n = 1;
while(q--){
string s; cin >> s;
int x, y; cin >> x >> y;
if(s=="Add"){
xr[timer] = y^xr[x];
adj[x].push_back(timer);
query.push_back({1, {x, timer++}});
n++;
}else{
query.push_back({0, {x, y}});
cntQ++;
}
}
reverse(all(query));
vector<pii> ett(n+1);
dfs(adj, 1, xr, ett);
int idx = cntQ-1;
vi ans(cntQ);
for(auto x: query){
if(x.ff==1){
trie->remove(ett[x.ss.ss].ff, xr[x.ss.ss]);
}else{
ans[idx--] = trie->query(xr[x.ss.ff], ett[x.ss.ss].ff, ett[x.ss.ss].ss);
}
}
for(auto x: ans) cout << x << endl;
return 1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int testcase = 1;
//cin >> testcase;
for(int tc = 1; tc <= testcase; tc++){
//cerr << "TESTCASE - " << tc << endl;
solve();
//cout << (solve() ? "YES" : "NO") << '\n';
cerr << endl;
}
return 0;
}