oj.uz

답안 #844930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
844930 2023-09-06T09:17:37 Z serifefedartar Klasika (COCI20_klasika) C++17
0 / 110
 522 ms 188160 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;
 
vector<pair<int,pair<int,int>>> queries;
vector<vector<int>> graph;
vector<set<int>> sets;
vector<int> val;
int tin[MAXN], tout[MAXN];
 
struct Node {
	Node *to[2];
	int id;
	Node () {
		to[0] = NULL;
		to[1] = NULL;
	}
};
 
int T = 0;
void dfs(int node, int parent) {
	tin[node] = ++T;
	for (auto u : graph[node])
		dfs(u, node);
	tout[node] = T;
}
 
bool check(Node *node, int subtree) {
	int st = tin[subtree];
	int en = tout[subtree];
	auto u = sets[node->id].lower_bound(st);
	if (u == sets[node->id].end() || *u > en)
		return false;
	return true;
}
 
int solve(Node *node, int subtree, int val) {
	int ans = 0;
	for (int i = 31; i >= 0; i--) {
		bool bit = ((1<<i) & val) != 0;
		if (node->to[!bit] != NULL && check(node->to[!bit], subtree)) {
			ans += (1<<i);
			node = node->to[!bit];
		} else if (node->to[bit] != NULL)
			node = node->to[bit];
		else
			return 0; 
	}
	return ans;
}
 
int main() {
	fast
	int Q;
	cin >> Q;
 
	queries = vector<pair<int,pair<int,int>>>(Q);
	graph = vector<vector<int>>(Q+5, vector<int>());
	val = vector<int>(Q+5, 0);
	int nodes = 1, a, b;
	string type;
	for (int i = 0; i < Q; i++) {
		cin >> type >> a >> b;
 
		if (type == "Add") {
			nodes++;
			val[nodes] = (val[a] ^ b);
			queries[i] = make_pair(1, make_pair(nodes, val[nodes]));
			graph[a].push_back(nodes);
		} else
			queries[i] = make_pair(0, make_pair(a, b));
	}
	dfs(1, 1);
 	
 	sets = vector<set<int>>(50*nodes, set<int>());
	Node *root = new Node();
	root->id = 1;
	int ids = 1;
	for (auto u : queries) {
		if (u.f) {
			Node *now = root;
			sets[now->id].insert(tin[u.s.f]);
			int x = u.s.s;
			for (int i = 31; i >= 0; i--) {
				bool bit = ((1<<i) & x) != 0;
				if (now->to[bit] == NULL) {
					now->to[bit] = new Node();
					now->to[bit]->id = ++ids;
				}
				now = now->to[bit];
				sets[now->id].insert(tin[u.s.f]);
			}
		} else {
			int node = u.s.f; 
			int subtree = u.s.s;
			Node *now = root;
			cout << solve(now, subtree, val[node]) << "\n";
		}
	}
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 522 ms 188160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -