oj.uz

Submission #223337

# Submission time Handle Problem Language Result Execution time Memory
223337 2020-04-15T07:25:15 Z oolimry Klasika (COCI20_klasika) C++14
11 / 110
 369 ms 524292 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int n = 1;
int cnt = 0;
static vector<int> adj[200005];
static int low[200005];
static int high[200005];
static int XOR[200005];
 
void dfs(int u){
	low[u] = cnt;
	high[u] = cnt;
	cnt++;
	for(int v : adj[u]){
		dfs(v);
		high[u] = max(high[u], high[v]);
	}
}
 
typedef pair<int,int> ii;
vector<ii> queries;

struct seg{
	bitset<400005> tree;
	
	void update(int i){
		for(i += n;i > 0;i >>= 1) tree[i] = 1;
	}
	
	int query(int l, int r){
		int res = 0;
		for(l += n, r += n;l < r;l >>= 1, r >>= 1){
			if(l&1) res |= tree[l++];
			if(r&1) res |= tree[--r];
		}
		return res;
	}
};

static unordered_map<int, seg> m[33];



int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int Q; cin >> Q;
	queries.push_back(ii(-1,0));
	
	while(Q--){
		string s; int a, b; 
		cin >> s >> a >> b;
		if(s[0] == 'A' || s[0] == 'a'){
			a--;
			assert(a < n);
			adj[a].push_back(n);
			XOR[n] = XOR[a] ^ b;
			queries.push_back(ii(-1,n));
			n++;
		}
		else{
			assert(a-1 < n);
			assert(b-1 < n);
			queries.push_back(ii(a-1,b-1));
		}
	}
	
	
	dfs(0);
	//for(int i = 0;i < n;i++) cout << low[i] << " " << high[i] << "\n";
	
	for(ii q : queries){
		//cout << q.first << " " << q.second << "\n";
		
		if(q.first == -1){
			int pos = low[q.second];
			int x = XOR[q.second];
			
			for(int b = 0;b <= 32;b++){
				m[b][x].update(pos);
				x ^= ((x & (1<<b)));
			}
			
			continue;
		}
		
		int other = XOR[q.first];
		int L = low[q.second], R = high[q.second];
		int cur = 0;
		for(int b = 32;b >= 0;b--){
			if((other & (1<<b)) == 0) cur ^= (1 << b);
			
			if(m[b][cur].query(L,R+1) == 0) cur ^= (1 << b);
		}
		
		cout << (cur ^ other) << "\n";
		
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107512 KB Output is correct
2 Correct 80 ms 128384 KB Output is correct
3 Correct 107 ms 183544 KB Output is correct
4 Correct 118 ms 206304 KB Output is correct
5 Correct 58 ms 83320 KB Output is correct
6 Correct 81 ms 135416 KB Output is correct
7 Correct 105 ms 178168 KB Output is correct
8 Correct 125 ms 209532 KB Output is correct
9 Correct 62 ms 99064 KB Output is correct
10 Correct 96 ms 156004 KB Output is correct
11 Correct 123 ms 190584 KB Output is correct
12 Correct 128 ms 211704 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107512 KB Output is correct
2 Correct 80 ms 128384 KB Output is correct
3 Correct 107 ms 183544 KB Output is correct
4 Correct 118 ms 206304 KB Output is correct
5 Correct 58 ms 83320 KB Output is correct
6 Correct 81 ms 135416 KB Output is correct
7 Correct 105 ms 178168 KB Output is correct
8 Correct 125 ms 209532 KB Output is correct
9 Correct 62 ms 99064 KB Output is correct
10 Correct 96 ms 156004 KB Output is correct
11 Correct 123 ms 190584 KB Output is correct
12 Correct 128 ms 211704 KB Output is correct
13 Runtime error 303 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107512 KB Output is correct
2 Correct 80 ms 128384 KB Output is correct
3 Correct 107 ms 183544 KB Output is correct
4 Correct 118 ms 206304 KB Output is correct
5 Correct 58 ms 83320 KB Output is correct
6 Correct 81 ms 135416 KB Output is correct
7 Correct 105 ms 178168 KB Output is correct
8 Correct 125 ms 209532 KB Output is correct
9 Correct 62 ms 99064 KB Output is correct
10 Correct 96 ms 156004 KB Output is correct
11 Correct 123 ms 190584 KB Output is correct
12 Correct 128 ms 211704 KB Output is correct
13 Runtime error 303 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -