oj.uz

Submission #223401

# Submission time Handle Problem Language Result Execution time Memory
223401 2020-04-15T08:48:33 Z dantoh000 Klasika (COCI20_klasika) C++14
66 / 110
 4062 ms 207732 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 13 ms 1280 KB Output is correct
14 Correct 15 ms 2048 KB Output is correct
15 Correct 15 ms 2816 KB Output is correct
16 Correct 15 ms 3456 KB Output is correct
17 Correct 13 ms 1152 KB Output is correct
18 Correct 14 ms 2048 KB Output is correct
19 Correct 14 ms 2688 KB Output is correct
20 Correct 16 ms 3456 KB Output is correct
21 Correct 14 ms 1152 KB Output is correct
22 Correct 16 ms 2048 KB Output is correct
23 Correct 16 ms 2688 KB Output is correct
24 Correct 15 ms 3328 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2685 ms 61336 KB Output is correct
2 Correct 3999 ms 112732 KB Output is correct
3 Correct 3977 ms 160484 KB Output is correct
4 Correct 3204 ms 206992 KB Output is correct
5 Correct 1708 ms 61304 KB Output is correct
6 Correct 2217 ms 112760 KB Output is correct
7 Correct 2361 ms 160632 KB Output is correct
8 Correct 1830 ms 207480 KB Output is correct
9 Correct 2684 ms 60884 KB Output is correct
10 Correct 3936 ms 113092 KB Output is correct
11 Correct 4062 ms 161244 KB Output is correct
12 Correct 3285 ms 207732 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 13 ms 1280 KB Output is correct
14 Correct 15 ms 2048 KB Output is correct
15 Correct 15 ms 2816 KB Output is correct
16 Correct 15 ms 3456 KB Output is correct
17 Correct 13 ms 1152 KB Output is correct
18 Correct 14 ms 2048 KB Output is correct
19 Correct 14 ms 2688 KB Output is correct
20 Correct 16 ms 3456 KB Output is correct
21 Correct 14 ms 1152 KB Output is correct
22 Correct 16 ms 2048 KB Output is correct
23 Correct 16 ms 2688 KB Output is correct
24 Correct 15 ms 3328 KB Output is correct
25 Correct 2685 ms 61336 KB Output is correct
26 Correct 3999 ms 112732 KB Output is correct
27 Correct 3977 ms 160484 KB Output is correct
28 Correct 3204 ms 206992 KB Output is correct
29 Correct 1708 ms 61304 KB Output is correct
30 Correct 2217 ms 112760 KB Output is correct
31 Correct 2361 ms 160632 KB Output is correct
32 Correct 1830 ms 207480 KB Output is correct
33 Correct 2684 ms 60884 KB Output is correct
34 Correct 3936 ms 113092 KB Output is correct
35 Correct 4062 ms 161244 KB Output is correct
36 Correct 3285 ms 207732 KB Output is correct
37 Incorrect 1697 ms 61348 KB Output isn't correct
38 Halted 0 ms 0 KB -