oj.uz

답안 #855909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855909 2023-10-02T08:54:18 Z wakandaaa Klasika (COCI20_klasika) C++17
110 / 110
 2069 ms 435380 KB 
#include<bits/stdc++.h>
// #define long long long
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 520
#endif

const int N = 2e5 + 5;
const int MOD = 1e9 + 7; // 998244353
const int inf = INT_MAX; // LLONG_MAX
const int LOG = 30;
template<class T> bool minimize(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool maximize(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> bool add(T &a, T b) { a += b; while (a > MOD) a -= MOD; return true; }

#define BIT(x, i) (((x) >> (i)) & 1)

struct TrieNode {
	set<int> s;
	TrieNode *child[2];
	TrieNode() {
		child[0] = child[1] = NULL;
	}
};

struct Trie {
	TrieNode *root;
	Trie() {
		root = new TrieNode();
	}
	void add(int value, int id) {
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			if (p->child[c] == NULL) p->child[c] = new TrieNode();
			p = p->child[c];
			p->s.insert(id);
		}
	}
	int get(int value, int L, int R) {
		int ans = 0;
		TrieNode *p = root;
		for (int i = LOG; i >= 0; --i) {
			int c = BIT(value, i);
			c ^= 1;
			if (p->child[c] == NULL || p->child[c]->s.lower_bound(L) == p->child[c]->s.upper_bound(R)) p = p->child[c ^ 1];
			else {
				ans += (1 << i);
				p = p->child[c];
			}
		}
		return ans;
	}
} trie;

struct Query {
	int type, x, y;
};

vector<pair<int, int> > g[N];
int St[N], Ft[N], Rxor[N];
vector<Query> Q;
int Time = 0;

void DFS(int u, int p, int L) {
	St[u] = ++Time;
	Rxor[u] = L;
	for (auto [v, w] : g[u]) if (v != p) {
		DFS(v, u, w ^ L);
	}
	Ft[u] = Time;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n = 1;
	int q; cin >> q;
	while (q--) {
		string s; cin >> s;
		int x, y; cin >> x >> y;
		--x;
		if (s == "Add") {
			Q.push_back({0, n, y});
			g[x].push_back({n, y});
			g[n].push_back({x, y});
			++n;
		} else {
			--y;
			Q.push_back({1, x, y});
		}
	}

	DFS(0, -1, 0);
	trie.add(0, St[0]);

	for (auto [type, x, y] : Q) {
		if (type == 0) trie.add(Rxor[x], St[x]);
		else cout << trie.get(Rxor[x], St[y], Ft[y]) << '\n';
	}

	return 0;
}
// I'm thinking out loud!

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7328 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7860 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7588 KB Output is correct
11 Correct 2 ms 7768 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7328 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7860 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7588 KB Output is correct
11 Correct 2 ms 7768 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 4 ms 8540 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 6 ms 11100 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 4 ms 8484 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 6 ms 11032 KB Output is correct
20 Correct 8 ms 12780 KB Output is correct
21 Correct 4 ms 8640 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 6 ms 11100 KB Output is correct
24 Correct 7 ms 12120 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 125764 KB Output is correct
2 Correct 885 ms 231732 KB Output is correct
3 Correct 1194 ms 332588 KB Output is correct
4 Correct 1479 ms 434616 KB Output is correct
5 Correct 536 ms 123676 KB Output is correct
6 Correct 915 ms 226956 KB Output is correct
7 Correct 1376 ms 326476 KB Output is correct
8 Correct 1823 ms 426000 KB Output is correct
9 Correct 528 ms 122976 KB Output is correct
10 Correct 884 ms 228140 KB Output is correct
11 Correct 1227 ms 328836 KB Output is correct
12 Correct 1594 ms 427832 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7772 KB Output is correct
5 Correct 2 ms 7328 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7860 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7588 KB Output is correct
11 Correct 2 ms 7768 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 4 ms 8540 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 6 ms 11100 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 4 ms 8484 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 6 ms 11032 KB Output is correct
20 Correct 8 ms 12780 KB Output is correct
21 Correct 4 ms 8640 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 6 ms 11100 KB Output is correct
24 Correct 7 ms 12120 KB Output is correct
25 Correct 589 ms 125764 KB Output is correct
26 Correct 885 ms 231732 KB Output is correct
27 Correct 1194 ms 332588 KB Output is correct
28 Correct 1479 ms 434616 KB Output is correct
29 Correct 536 ms 123676 KB Output is correct
30 Correct 915 ms 226956 KB Output is correct
31 Correct 1376 ms 326476 KB Output is correct
32 Correct 1823 ms 426000 KB Output is correct
33 Correct 528 ms 122976 KB Output is correct
34 Correct 884 ms 228140 KB Output is correct
35 Correct 1227 ms 328836 KB Output is correct
36 Correct 1594 ms 427832 KB Output is correct
37 Correct 969 ms 126312 KB Output is correct
38 Correct 1403 ms 231008 KB Output is correct
39 Correct 1663 ms 335468 KB Output is correct
40 Correct 1772 ms 435380 KB Output is correct
41 Correct 961 ms 123892 KB Output is correct
42 Correct 1431 ms 227176 KB Output is correct
43 Correct 1766 ms 326972 KB Output is correct
44 Correct 2069 ms 425348 KB Output is correct
45 Correct 1105 ms 123324 KB Output is correct
46 Correct 1667 ms 227968 KB Output is correct
47 Correct 1818 ms 328040 KB Output is correct
48 Correct 1906 ms 427872 KB Output is correct