Submission #211220

#	Time	Username	Problem	Language	Result	Execution time	Memory
211220		sm1ley	Klasika (COCI20_klasika)	C++17	110 / 110	3119 ms	452128 KiB

klasika

#include <vector>
#include <set>
#include <iostream>
#define ll long long
#define endl "\n"
#define IOS cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;

const int N = 2e5+13;
struct Query{
    int t,x,y;
};
struct Node{
    set<int> times;
    Node *bit[2];
    Node(){
        bit[0]=bit[1]=NULL;
    }
};
Node trie;

int timer;
int tin[N], tout[N];
int xr[N]; //distance from node 1 to node i
vector<pair<int,int>> g[N];
vector<Query> question;

void dfs(int v,int p,int val){
    tin[v]=++timer;
    xr[v]=xr[p]^val;
    for(auto t:g[v]){
        if(t.first==p)continue;
        dfs(t.first,v,t.second);
    }
    tout[v]=timer;//++;
}

void insert(int val,int num){
    Node *t = &trie;
    for(int i=30;i>=-1;i--){
        t->times.insert(num);
        if(val&(1<<i)){
            if(t->bit[1]==NULL)t->bit[1]=new Node();
            t = t->bit[1];
        }else{
            if(t->bit[0]==NULL)t->bit[0]=new Node();
            t = t->bit[0];
        }
    }
}
bool can(set<int> &a,int in,int out){
    return a.lower_bound(in)==a.upper_bound(out);
}

//
void get(int val,int in,int out){
    Node *t = &trie;
    int ans = 0;
    for(int i=30;i>=0;i--){
        if(val&(1<<i)){//ned 0
            if(t->bit[0]==NULL || can(t->bit[0]->times,in,out)){
                t = t->bit[1];
            }else{
                t = t->bit[0];
                ans |= (1<<i);
            }
        }
        else{ //ned 1
            if(t->bit[1]==NULL||can(t->bit[1]->times,in,out)){
                t = t->bit[0];
            }else{
                ans |= (1<<i);
                t = t->bit[1];
            }
        }
    }
    cout<<ans<<endl;
}

int q;
int main(){
    IOS;
    cin>>q;
    int num=2;
    for(int i=0;i<q;i++){
        string s;cin>>s;
        int a,b;cin>>a>>b;
        if(s=="Add"){
            question.push_back({1,num,a});
            g[a].push_back({num,b});
            g[num].push_back({a,b});
            num++;
        }
        if(s=="Query")question.push_back({2,a,b});
    }
    dfs(1,1,0);
    insert(0,tin[1]);
    for(int i=0;i<q;i++){
        int t=question[i].t;
        int x=question[i].x;
        int y=question[i].y;
        if(t==1) insert(xr[x],tin[x]);    
        else get(xr[x],tin[y],tout[y]);
    }
    return 0;
}

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