oj.uz

Submission #344490

# Submission time Handle Problem Language Result Execution time Memory
344490 2021-01-06T02:06:25 Z limabeans Klasika (COCI20_klasika) C++17
110 / 110
 2695 ms 445316 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


const int LOG = 30;

int q;
char typ[maxn];
int x[maxn], y[maxn];


int tin[maxn];
int tout[maxn];
int dp[maxn];
vector<pair<int,int>> g[maxn];
int cloc = 0;

void dfs(int at, int p) {
    tin[at] = cloc++;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dp[to] = dp[at] ^ ed.first;
	dfs(to, at);
    }
    tout[at] = cloc++;
}

struct node {
    set<int> st;
    node *ch[2];
    node() {
	ch[0] = ch[1] = NULL;
    }

    bool inrange(int in, int out) {
	auto iter = st.lower_bound(in);
	return iter!=st.end() && *iter<=out;
    }
};


void insert(node *at, int val, int enterTime) {
    for (int i=LOG-1; i>=0; i--) {
	int bit = val>>i&1;
	if (at->ch[bit] == NULL) {
	    at->ch[bit] = new node();
	}
	at = at->ch[bit];
	at->st.insert(enterTime);	
    }

}

node *root;

int qry(int val, int in, int out) {
    assert(in<=out);
    
    node *at = root;
    int res = 0;
    for (int i=LOG-1; i>=0; i--) {
	int bit = val>>i&1;
	if (at->ch[bit^1] == NULL || !at->ch[bit^1]->inrange(in, out)) {
	    at = at->ch[bit];
	    res |= (bit<<i);
	} else {
	    at = at->ch[bit^1];
	    res |= ((bit^1)<<i);
	}
    }

    return res^val;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    
    root = new node();
    cin>>q;

    
    int n = 1;
    
    for (int i=0; i<q; i++) {
	string op;
	cin>>op;
	typ[i]=op[0];
	cin>>x[i];
	cin>>y[i];
	
	if (typ[i]=='A') {
	    ++n;
	    g[x[i]].push_back({y[i], n});
	    x[i] = n;
	}

    }

    dfs(1, 0);
    insert(root, dp[1], tin[1]);
    

    for (int i=0; i<q; i++) {
	if (typ[i]=='A') {
	    int at = x[i];
	    insert(root, dp[at], tin[at]);
	} else {
	    int a = x[i];
	    int b = y[i];
	    int res = qry(dp[a], tin[b], tout[b]);
	    cout<<res<<"\n";
	}
    }
    
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24044 KB Output is correct
2 Correct 15 ms 24172 KB Output is correct
3 Correct 16 ms 24300 KB Output is correct
4 Correct 16 ms 24428 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 16 ms 24300 KB Output is correct
8 Correct 16 ms 24428 KB Output is correct
9 Correct 16 ms 24044 KB Output is correct
10 Correct 16 ms 24172 KB Output is correct
11 Correct 16 ms 24300 KB Output is correct
12 Correct 16 ms 24428 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24044 KB Output is correct
2 Correct 15 ms 24172 KB Output is correct
3 Correct 16 ms 24300 KB Output is correct
4 Correct 16 ms 24428 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 16 ms 24300 KB Output is correct
8 Correct 16 ms 24428 KB Output is correct
9 Correct 16 ms 24044 KB Output is correct
10 Correct 16 ms 24172 KB Output is correct
11 Correct 16 ms 24300 KB Output is correct
12 Correct 16 ms 24428 KB Output is correct
13 Correct 19 ms 25324 KB Output is correct
14 Correct 20 ms 26604 KB Output is correct
15 Correct 22 ms 27884 KB Output is correct
16 Correct 24 ms 29036 KB Output is correct
17 Correct 18 ms 25196 KB Output is correct
18 Correct 21 ms 26476 KB Output is correct
19 Correct 22 ms 27756 KB Output is correct
20 Correct 25 ms 28780 KB Output is correct
21 Correct 18 ms 25196 KB Output is correct
22 Correct 20 ms 26476 KB Output is correct
23 Correct 22 ms 27756 KB Output is correct
24 Correct 23 ms 28780 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 139884 KB Output is correct
2 Correct 1189 ms 244276 KB Output is correct
3 Correct 1696 ms 344428 KB Output is correct
4 Correct 2251 ms 444908 KB Output is correct
5 Correct 752 ms 137196 KB Output is correct
6 Correct 1263 ms 238956 KB Output is correct
7 Correct 1773 ms 336236 KB Output is correct
8 Correct 2298 ms 433440 KB Output is correct
9 Correct 759 ms 136940 KB Output is correct
10 Correct 1286 ms 239852 KB Output is correct
11 Correct 1804 ms 338812 KB Output is correct
12 Correct 2320 ms 436012 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24044 KB Output is correct
2 Correct 15 ms 24172 KB Output is correct
3 Correct 16 ms 24300 KB Output is correct
4 Correct 16 ms 24428 KB Output is correct
5 Correct 16 ms 24044 KB Output is correct
6 Correct 16 ms 24172 KB Output is correct
7 Correct 16 ms 24300 KB Output is correct
8 Correct 16 ms 24428 KB Output is correct
9 Correct 16 ms 24044 KB Output is correct
10 Correct 16 ms 24172 KB Output is correct
11 Correct 16 ms 24300 KB Output is correct
12 Correct 16 ms 24428 KB Output is correct
13 Correct 19 ms 25324 KB Output is correct
14 Correct 20 ms 26604 KB Output is correct
15 Correct 22 ms 27884 KB Output is correct
16 Correct 24 ms 29036 KB Output is correct
17 Correct 18 ms 25196 KB Output is correct
18 Correct 21 ms 26476 KB Output is correct
19 Correct 22 ms 27756 KB Output is correct
20 Correct 25 ms 28780 KB Output is correct
21 Correct 18 ms 25196 KB Output is correct
22 Correct 20 ms 26476 KB Output is correct
23 Correct 22 ms 27756 KB Output is correct
24 Correct 23 ms 28780 KB Output is correct
25 Correct 689 ms 139884 KB Output is correct
26 Correct 1189 ms 244276 KB Output is correct
27 Correct 1696 ms 344428 KB Output is correct
28 Correct 2251 ms 444908 KB Output is correct
29 Correct 752 ms 137196 KB Output is correct
30 Correct 1263 ms 238956 KB Output is correct
31 Correct 1773 ms 336236 KB Output is correct
32 Correct 2298 ms 433440 KB Output is correct
33 Correct 759 ms 136940 KB Output is correct
34 Correct 1286 ms 239852 KB Output is correct
35 Correct 1804 ms 338812 KB Output is correct
36 Correct 2320 ms 436012 KB Output is correct
37 Correct 1323 ms 140852 KB Output is correct
38 Correct 1858 ms 244332 KB Output is correct
39 Correct 2229 ms 346860 KB Output is correct
40 Correct 2503 ms 445316 KB Output is correct
41 Correct 1464 ms 137836 KB Output is correct
42 Correct 1973 ms 238700 KB Output is correct
43 Correct 2295 ms 336236 KB Output is correct
44 Correct 2609 ms 432492 KB Output is correct
45 Correct 1553 ms 137580 KB Output is correct
46 Correct 2106 ms 239980 KB Output is correct
47 Correct 2448 ms 337516 KB Output is correct
48 Correct 2695 ms 435820 KB Output is correct