oj.uz

Submission #223258

# Submission time Handle Problem Language Result Execution time Memory
223258 2020-04-15T06:22:09 Z oolimry Klasika (COCI20_klasika) C++14
0 / 110
 5000 ms 33160 KB 
#include <bits/stdc++.h>

using namespace std;

int n = 1;
int cnt = 0;
vector<int> adj[200005];
int low[200005];
int high[200005];
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;

unordered_map<int, set<int> > m[32];

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 33160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -