Submission #198497

#	Time	Username	Problem	Language	Result	Execution time	Memory
198497		alishahali1382	Klasika (COCI20_klasika)	C++14	33 / 110	5109 ms	498192 KiB

klasika

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define get(x, y) (((x)>>(y))&1)
 
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 200010, LOG=31;
 
int n=1, m, k, u, v, x, y, t, L, R, X, ans;
int TR[MAXN*LOG][2], ts;
int par[MAXN], val[MAXN];
int stt[MAXN], fnt[MAXN], timer;
int typ[MAXN], A[MAXN], B[MAXN];
vector<int> G[MAXN];
set<int> vec[MAXN*LOG];
string s;
 
bool f(int v, int l, int r){
    auto it=vec[v].lower_bound(l);
    if (it==vec[v].end() || r<=*it) return 0;
    return 1;
}
 
void dfs(int node){
    stt[node]=timer++;
    for (int v:G[node]) dfs(v);
    fnt[node]=timer;
}
 
void Add(int X, int pos){
    int v=0;
    for (int i=LOG-1; ~i; i--){
        int c=get(X, i);
        if (!TR[v][c]) TR[v][c]=++ts;
        v=TR[v][c];
        vec[v].insert(pos);
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>m;
    for (int i=1; i<=m; i++){
        cin>>s>>A[i]>>B[i];
        if (s=="Add"){
            par[++n]=A[i];
            val[n]=val[A[i]]^B[i];
            G[A[i]].pb(n);
            continue ;
        }
        typ[i]=1;
    }
    dfs(1);
    n=1;
    Add(0, stt[1]);
    
    for (int i=1; i<=m; i++){
        if (typ[i]){
            X=val[A[i]];    
            L=stt[B[i]];
            R=fnt[B[i]];
            ans=0;
            
            int v=0;
            for (int i=LOG-1; ~i; i--){
                int c=get(X, i)^1;
                if (TR[v][c] && f(TR[v][c], L, R)) ans|=(1<<i);
                else c^=1;
                v=TR[v][c];
            }
            
            cout<<ans<<'\n';
            continue ;
        }
        ++n;
        Add(val[n], stt[n]);
    }
    
    
    
    return 0;
}

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