제출 #1135254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135254		damoon	Klasika (COCI20_klasika)	C++20	33 / 110	1561 ms	539804 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 int L = 2e5+10,lg = 30;
const int inf = 1e9+10;
int n,q;
int parv[L],root[L];
vector<int> ch[L];
int st[L],fn[L];
vector<int> ans;
int tim;

random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)

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{
    int mode,u,v;
    que(){
        mode = u = v = 0;
    }
}ask[L];

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

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

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

    int get(int x,int d,int l,int r){
        if(d == -1)
            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(int v){
    tim++;
    st[v] = tim;
    for(auto u:ch[v]){
        root[u] = root[v]^parv[u];
        dfs(u);
    }
    tim++;
    fn[v] = tim;
}

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(int i=1;i<=q;i++){
        string mode;
        int 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;
        }
    }
    dfs(1);
    T.update(0,lg,st[1]);
    for(int t=1;t<=q;t++){
        int u = ask[t].u;
        int v = ask[t].v;
        if(ask[t].mode == 0){
            T.update(root[u],lg,st[u]);
        }
        else{
            ans.pb(T.get(root[u],lg,st[v],fn[v]));
        }
    }
    for(auto i:ans)
        cout<<i<<'\n';
}

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