Submission #223660

#	Time	Username	Problem	Language	Result	Execution time	Memory
223660		dantoh000	Klasika (COCI20_klasika)	C++14	110 / 110	3055 ms	474032 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef pair<int,int> ii;
typedef pair<char,ii> Query;
vector<Query> queries;
vector<int> adjlist[N];
const int INF = 1000000000;
int num[N], l[N], r[N];
int ct = 1;

struct node{
    int s,e,m;
    set<int> v;
    node *l = NULL, *r = NULL;
    node (int _s, int _e): s(_s), e(_e){
        m = (s+e)/2;
    }
    void up(int x, int nv){
        //printf("update %d %d %d\n",s,e,x);
        v.insert(nv);
        if (s == e){
            return;
        }
        if (x <= m){
            if (l == NULL) l = new node(s,m);
            l->up(x,nv);
        }
        else{
            if (r == NULL) r = new node(m+1,e);
            r->up(x,nv);
        }
    }
    int query(int id, int x, int L, int R){
        //printf("segment tree: %d %d %d %d\n",s,e,id,x);
        if (s == e){
            return s^x;
        }
        if (x & (1<<id)){
            //printf("prefer left\n");
            if (l == NULL || l->v.lower_bound(L) == l->v.end() || *(l->v.lower_bound(L)) > R){
                //printf("right anyway\n");
                return r->query(id-1,x,L,R);
            }
            else return l->query(id-1,x,L,R);
        }
        else{
            //printf("prefer right\n");
            if (r == NULL || r->v.lower_bound(L) == r->v.end() || *(r->v.lower_bound(L)) > R) {
                //printf("left anyway\n");
                return l->query(id-1,x,L,R);
            }
            else return r->query(id-1,x,L,R);
        }
    }
}*root;
void dfs(int u, int p){
    l[u] = ct++;
    for (auto v : adjlist[u]){
        if (v == p) continue;
        dfs(v,u);
    }
    r[u] = ct++;
}
int main() {
	int q;
	cin >> q;
    root = new node(0,(int)((unsigned)(1<<31)-1));
	while (q--) {
        string Q;
        int a,b;
		cin >> Q >> a >> b;
		queries.push_back({Q[0],{a,b}});
		if (Q == "Add"){
            num[++ct] = num[a]^b;
            adjlist[a].push_back(ct);
		}
	}
	ct = 1;
	dfs(1,-1);
	root->up(0,l[1]);
	ct = 1;
	for (auto qu : queries){
        char Q = qu.first;
        int a = qu.second.first, b = qu.second.second;
        if (Q == 'A'){
            ct++;
            root->up(num[ct],l[ct]);
        }
        else{
            printf("%d\n",root->query(30,num[a],l[b],r[b]));
        }
	}
	return 0;
}

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