제출 #839134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839134		kingmessi	Klasika (COCI20_klasika)	C++17	33 / 110	1705 ms	524288 KiB

klasika

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x) 
#define btz(x) __builtin_ctz(x)
using namespace std;

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
  
int power( int N, int M){
    int power = N, sum = 1;
    if(N == 0) sum = 0;
    while(M > 0){if((M & 1) == 1){sum *= power;}
    power = power * power;M = M >> 1;}
    return sum;
}

const int N=200005;
vector<pii> adj[N];
int st[N],en[N],et=0;
int d[N];
bool visited[N];
 
void dfs(int current){
st[current]=et++;
visited[current]=true;
    for(auto next_vertex : adj[current]){
        if(visited[next_vertex.ff])continue;
        d[next_vertex.ff]=d[current]^(next_vertex.ss);
        dfs(next_vertex.ff);
    }
en[current]=et;
}

const int SZ = 6000001;
const int MXBIT = 30;
si s[SZ];
int nex[SZ][2],num = 0;
void ins(int node) {
    int x = d[node];
    int cur = 0;
    s[cur].insert(st[node]);
    rrep(i,MXBIT,0) {
        int t = (x>>i)&1;
        if (!nex[cur][t]) {nex[cur][t] = ++num;}
        cur = nex[cur][t];
        s[cur].insert(st[node]);
    }
}

int test(int a,int b) {
    int x = d[a];
    // cout<<x<<" "<<a<<" "<<b<<endl;
    int cur = 0;
    rrep(i,MXBIT,0) {
        int t = ((x>>i)&1)^1;
        if (!nex[cur][t]){
            t^=1;
        }
        else{
            auto it = s[nex[cur][t]].lb(st[b]);
            if(it != s[nex[cur][t]].end()){
                int res = *(it);
                if(res >= en[b])t^=1;
            }
            else t^=1;
        }
        cur = nex[cur][t]; if (t) x ^= 1LL<<i;
        // cout<<cur<<"hi"<<endl;
    }
    return x;
}



void solve()
{
    vector<pair<string, pii>> qry;
    int node = 1;
    int q;cin>>q;
    rep(i,0,q){
        string op;
        cin>>op;
        int a,b;
        cin>>a>>b;
        qry.pb({op,{a,b}});
        if(op == "Add"){
            node++;
            adj[a].pb({node,b});
        }
    }
    dfs(1);
    // give(d,node+1);cout<<endl;
    // give(st,node+1);cout<<endl;
    // give(en,node+1);cout<<endl;
    node = 1;
    ins(1);
    rep(i,0,q){
        string op = qry[i].ff;
        int a = qry[i].ss.ff;
        int b = qry[i].ss.ss;
        if(op == "Add"){
            node++;
            ins(node);
        }
        else{
            int ans = test(a,b);
            // cout<<"ans"<<endl;
            cout<<ans<<endl;
        }
    }
    // cout<<num<<endl;
    // rep(i,0,num+1){
    //     for(auto x : s[i])cout<<x<<" ";cout<<"end"<<endl;
    // }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
        solve();
    return 0;
}

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