Submission #889425

#	Time	Username	Problem	Language	Result	Execution time	Memory
889425		Alish	Klasika (COCI20_klasika)	C++17	110 / 110	2057 ms	424024 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);


ll mod = 1e9+7 ;

const int N = 2e5+23, L=31;


int h[N];
struct node {
	node* ch[2];
	set<int> ss;

	node() {
		ch[0] = ch[1] = nullptr;
	}
}root;

int st[N], ft[N], tim=0;
vector<int> g[N];
vector<pair<int, pii> > Q;
int cnt=1;
int tr;

void dfs(int v){
    st[v]=tim++;
    for (int u: g[v]) dfs(u);
    ft[v]=tim;
}

void add(int x, int pp){
    node* cur=&root;

    for (int i=L-1; i>=0; i--){
        int t=(x>>i&1);
        if(cur->ch[t]==nullptr) cur->ch[t]= new node();

        cur=cur->ch[t];
        cur->ss.insert(pp);
    }
}

int get(int x, int v){
    node* cur=&root;
    int ans=0;
    for (int i=L-1; i>=0; i--){
        int t=(x>>i&1);
        t=1-t;
        if(cur->ch[t]!=nullptr){
            auto x=cur->ch[t]->ss.lower_bound(st[v]);

            if(x==cur->ch[t]->ss.end() || *x>=ft[v]){
                cur=cur->ch[1-t];
            }
            else{
                ans+=(1<<i);
                cur=cur->ch[t];
            }
        }
        else{
            cur=cur->ch[1-t];
        }
    }
    return ans;
}

int main()
{
    fast_io
    int q; cin>>q;
    for (int i=0; i<q; i++){
        string s; cin>>s;
        if(s=="Add"){
             ll u, w;
            cin>>u>>w;
            cnt++;
            h[cnt]=h[u]^w;
            g[u].pb(cnt);
            Q.pb({0, {cnt, u}});
        }
        else{
                int u, v; cin>>v>>u;
            Q.pb({1, {v, u}});
        }
    }
    dfs(1);

    for (int i=0; i<=cnt; i++){
        g[i].clear();
        g[i].shrink_to_fit();
    }
    add(0, st[1]);

    for (auto pp: Q){
        int t=pp.F, v=pp.S.F, u=pp.S.S;
        if(!t){
            add(h[v], st[v]);
        }
        else{
            cout<<get(h[v], u)<<endl;
        }
    }

}

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