제출 #1135258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135258		damoon	Klasika (COCI20_klasika)	C++20	33 / 110	853 ms	554872 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<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> 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 = 262144,lg = 30;
const int inf = 1e9+10;
int n,q;
vector<int> ch[L];
int par[L],xr[L];
int root[L];
int st[L],fn[L],h[L];
vector<int> tr;
int ind[L],en[L];
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;}

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

struct trie{
    trie* ch[2];
    trie(){
        ch[0] = nullptr;
        ch[1] = nullptr;
    }

    void spread(int c){
        if(ch[c] != nullptr)
            return;
        ch[c] = new trie();
    }
    void update(int x,int ind){
        if(ind == -1)
            return;
        int c = dig(x,ind);
        spread(c);
        ch[c]->update(x,ind-1);
    }
    int get(int x,int ind){
        if(ch[0] == nullptr and ch[1] == nullptr)
            return 0;
        int c = dig(x,ind);
        if(ch[1-c] != nullptr)
            return (1<<ind) + ch[1-c]->get(x,ind-1);
        else
            return ch[c]->get(x,ind-1);
    }
};

struct que{
    int u,v,mode;
};
vector<que> ask;

void dfs(int v){
    tim++;
    st[v] = tim;
    ind[v] = tr.size();
    tr.pb(v);
    for(auto u:ch[v]){
        root[u] = root[v]^xr[u];
        h[u] = h[v]+1;
        dfs(u);
    }
    tim++;
    fn[v] = tim;
}

bool ispar(int u,int v){
    if(v > n)
        return false;
    return (st[u] <= st[v] and fn[u] >= fn[v]);
}

//seg
trie T[L*2];
void update(int id,int l,int r,int ind,int x){
    T[id].update(x,lg);
    if(l+1 == r)
        return;
    int mid = (l+r)>>1;
    if(ind < mid)
        update(lc,l,mid,ind,x);
    else
        update(rc,mid,r,ind,x);
}

int get(int id,int l,int r,int l2,int r2,int x){
    if(l==l2 and r==r2)
        return T[id].get(x,lg);
    int mid = (l+r)>>1;
    int ans = 0;
    if(l2 < mid)
        ans = max(ans,get(lc,l,mid,l2,min(r2,mid),x));
    if(r2 > mid)
        ans = max(ans,get(rc,mid,r,max(l2,mid),r2,x));
    return ans;
}

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;
        que tmp;
        if(mode == "Add"){
            n++;
            tmp.mode = 0;
            tmp.u = n;
            par[n] = x;
            xr[n] = y;
            ch[x].pb(n);
        }
        else{
            tmp.mode = 1;
            tmp.u = x;
            tmp.v = y;
        }
        ask.pb(tmp);
    }
    tr.pb(0);
    dfs(1);
    tr.pb(n+1);
    for(int v=1;v<=n;v++){
        int l = ind[v],r = n+1;
        while(r-l>1){
            int mid = (l+r)>>1;
            if(ispar(v,tr[mid]))
                l = mid;
            else
                r = mid;
        }
        en[v] = r;
    }
    update(1,1,L+1,ind[1],0);
    for(auto t:ask){
        int u = t.u;
        int v = t.v;
        if(t.mode == 0){
            update(1,1,L+1,ind[u],root[u]);
        }
        else{
            cout<<get(1,1,L+1,ind[v],en[v],root[u])<<endl;
        }
    }
}

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