Submission #223401

#	Time	Username	Problem	Language	Result	Execution time	Memory
223401		dantoh000	Klasika (COCI20_klasika)	C++14	66 / 110	4062 ms	207732 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int LOGN = 20;
int num[N], d[N];
int p[N][LOGN];
int sz;
int ct = 1;
struct node{
    int s,e,m,v;
    node *l = NULL, *r = NULL;
    node (int _s, int _e): s(_s), e(_e){
        m = (s+e)/2;
        v = 0;
    }
    void build(){
        l = new node(s,m);
        r = new node(m+1,e);
    }
    void up(int x){
        //printf("update %d %d %d\n",s,e,x);
        v = 1;
        if (s == e){
            return;
        }
        if (x <= m){
            if (l == NULL) build();
            l->up(x);
        }
        else{
            if (r == NULL) build();
            r->up(x);
        }
    }
    int query(int id, int x){
        //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 == 0){
                //printf("right anyway\n");
                return r->query(id-1,x);
            }
            else return l->query(id-1,x);
        }
        else{
            //printf("prefer right\n");
            if (r == NULL || r->v == 0) {
                //printf("left anyway\n");
                return l->query(id-1,x);
            }
            else return r->query(id-1,x);
        }
    }
}*root;
int is_parent(int u, int v){
    int dif = d[u] - d[v];
    if (dif < 0) return 0;
    while (dif){
        int lsb = 31-__builtin_clz(dif);
        u = p[u][lsb];
        dif -= (1<<lsb);
    }
    return (u==v);
}
int main() {
	int q;
	cin >> q;
    root = new node(0,(int)((unsigned)(1<<31)-1));
    root -> up(0);
	while (q--) {
        string Q;
        int a,b;
		cin >> Q >> a >> b;
		if (Q == "Add"){
            num[++ct] = num[a]^b;
            //printf("added %d %d\n",ct,num[ct]);
            p[ct][0] = a;
            d[ct] = d[a]+1;
            for (int k = 1; k < LOGN; k++){
                if (p[ct][k-1] == -1) break;
                p[ct][k] = p[p[ct][k-1]][k-1];
            }
            root->up(num[ct]);
		}
        else if (Q == "Query"){
            if (q <= 2000){
                int ans = 0;
                for (int i = 1; i <= ct; i++){
                    if (is_parent(i,b)){
                        ans = max(ans,num[i]^num[a]);
                    }
                }
                printf("%d\n",ans);
            }
            else{
                printf("%d\n",root->query(30,num[a]));
            }
        }
	}
	return 0;
}

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