oj.uz

답안 #223336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223336 2020-04-15T07:23:33 Z dantoh000 Klasika (COCI20_klasika) C++14
0 / 110
 307 ms 7424 KB 
#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;
            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]);
            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);
            }
        }
	}
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 307 ms 7424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -