Submission #210770

#	Time	Username	Problem	Language	Result	Execution time	Memory
210770		sm1ley	Klasika (COCI20_klasika)	C++17	0 / 110	90 ms	24820 KiB

klasika

#include <bits/stdc++.h>
#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{
    int depth;
    set<int> nodes;
    Node *bit[2];
};
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=31;i>=0;i--){
        t->nodes.insert(num);
        if(val&(1<<i)){
            t = t->bit[1];
        }else{
            t = t->bit[0];
        }
    }
}
bool parent(int u,int v){ //is u parten to v
    return tin[u]<=tin[v]&&tout[u]>=tout[v];
}

bool can(set<int> &nodes,int a,int b){
    bool out=0;
    for(auto x:nodes){
        out |= parent(a,x)|parent(b,x);
    }
    return out;
}

//
void get(int val,int a,int b){
    Node *t = trie;
    for(int i=31;i>=0;i--){
        if(val&(1<<i) && can(t->bit[0]->nodes,a,b) ){
            t = t->bit[0];
        }else if(val&(1<<i)){
            cout<<val<<endl;
            return;
        }else if(can(t->bit[1]->nodes,a,b)){
            val^=(1<<i);
        }
    }
    cout<<val<<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=="Query")question.push_back({2,a,b});
        if(s=="Add"){
            question.push_back({1,a,b});
            g[a].push_back({num,b});
            g[num].push_back({a,b});
            num++;
        }
    }
    dfs(1,1,0);
    num=2;
    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(y,num++);    
        else get(xr[x]^xr[y],x,y);
    }
    return 0;
}

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