제출 #1135229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135229		damoon	Klasika (COCI20_klasika)	C++17	0 / 110	879 ms	285192 KiB

klasika

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

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long

typedef pair<ll,ll> pii;
typedef pair<ll,pii> pip;
typedef pair<pii,ll> ppi;
#define f first
#define s second

#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

#define pb(x) push_back(x)
#define pp() pop_back()

#define lc id<<1
#define rc lc|1

const ll L = 2e5+10,lg = 30;
const ll inf = 1e9+10;
ll n,q;
ll parv[L],root[L];
vector<ll> ch[L],tr;
ll st[L],fn[L];

void pr(int* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void pr(long long* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void pr(pii* vv,int l,int r){for(int i=l;i<r;i++){cout<<"("<<vv[i].f<<" , "<<vv[i].s<<")  ";}cout<<endl;}
void pr(vector<int> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void pr(vector<long long> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void pr(vector<pii> vv){for(auto i:vv){cout<<"("<<i.f<<" , "<<i.s<<")  ";}cout<<endl;}

struct que{
    ll mode,u,v;
}ask[L];

bool dig(ll x,ll d){
    return (((1<<d)&x) > 0);
}

struct trie{
    set<ll> ind;
    trie* ch[2];
    trie(){
        ch[0] = nullptr;
        ch[1] = nullptr;
        ind.insert(inf);
    }

    void spread(){
        if(ch[0] == nullptr){
            ch[0] = new trie();
            ch[1] = new trie();
        }
    }
    void update(ll x,ll d,ll idx){
        ind.insert(idx);
        if(d == -1){
            return;
        }
        spread();
        bool c = dig(x,d);
        ch[c]->update(x,d-1,idx);
    }

    ll get(ll x,ll d,ll l,ll r){
        if(ch[0] == nullptr and ch[1] == nullptr)
            return 0;
        bool c = dig(x,d);
        if(ch[1-c] != nullptr){
            if(*ch[1-c]->ind.lower_bound(l) <= r)
                return (1<<d) + ch[1-c]->get(x,d-1,l,r);
            else
                return ch[c]->get(x,d-1,l,r); 
        }
        else
            return ch[c]->get(x,d-1,l,r);
    }
}T;

void dfs(ll v){
    st[v] = tr.size();
    tr.pb(v);
    for(auto u:ch[v]){
        root[u] = root[v]^parv[u];
        dfs(u);
    }
    fn[v] = tr.size();
    tr.pb(v);
}

int main(){
    //ofstream cout ("out.txt");
    //ifstream cin ("in.txt");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n = 1;
    cin>>q;
    for(ll i=1;i<=q;i++){
        string mode;
        ll x,y;
        cin>>mode>>x>>y;
        if(mode == "Add"){
            n++;
            ask[i].mode = 0;
            ask[i].u = n;
            parv[n] = y;
            ch[x].pb(n);
        }
        else{
            ask[i].mode = 1;
            ask[i].u = x;
            ask[i].v = y;
        }
    }
    ch[0].pb(1);
    dfs(0);
    for(ll t=1;t<=q;t++){
        ll u = ask[t].u;
        ll v = ask[t].v;
        if(ask[t].mode == 0){
            T.update(root[u],lg,st[u]);
            T.update(root[u],lg,fn[u]);
        }
        else{
            cout<<T.get(root[u],lg,st[v],fn[v])<<endl;
        }
    }
}

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