Submission #223340

#	Time	Username	Problem	Language	Result	Execution time	Memory
223340		dantoh000	Klasika (COCI20_klasika)	C++14	33 / 110	2533 ms	5548 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, LOG_A = 31;
const int LOGN = 20;
int k;
int basis[LOG_A];
int num[N], d[N];
int p[N][LOGN];
int sz;
int ct = 1;
void insertVector(int mask) {
	for (int i = 0; i < LOG_A; i++) {
		if ((mask & (1<<i)) == 0) continue;
		if (!basis[i]) {
			basis[i] = mask;
			++sz;
			return;
		}
		mask ^= basis[i];
	}
}
int maxxor(int cur){
    for (int i = LOG_A; i >= 0; i--){
        if ((cur & (1<<i)) == 0){
            if (basis[i]){
                cur ^= basis[i];
                return cur;
            }
        }
    }
}
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;
	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];
            }
            insertVector(num[ct]);
		}
        else if (Q == "Query"){
            int temp = maxxor(num[a]);
            //printf("%d %d\n",a,temp);
            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]);
                    }
                }
                //if (b == 1) assert(temp == ans);
                printf("%d\n",ans);
            }
            else printf("%d\n",temp);
        }
	}
	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int maxxor(int)':
klasika.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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