oj.uz

Submission #674007

# Submission time Handle Problem Language Result Execution time Memory
674007 2022-12-22T14:25:29 Z chanhchuong123 Klasika (COCI20_klasika) C++14
110 / 110
 2113 ms 437272 KB 
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 200005;
int n;
int numNode;
int h[N], timer;
string op; int a, b;
int tin[N], tout[N];
vector<pair<int, int>> adj[N];
pair<string, pair<int, int>> q[N];

struct Trie {
	Trie* nxt[2];
	set<int> se;
	Trie() {
		nxt[0] = nxt[1] = nullptr;
		se.clear();
	}
} *root;

void add(int u) {
	Trie *p = root;
	int x = h[u], id = tin[u];
	for (int i = 30; i >= 0; --i) {
		int LOVE = x >> i & 1;
		if (p->nxt[LOVE] == nullptr) p->nxt[LOVE] = new Trie();
		p = p->nxt[LOVE]; p->se.insert(id);
	}
}

bool check(Trie *p, int l, int r) {
	if (p->se.empty()) return false;
	auto it = p->se.lower_bound(l);
	if (it == p->se.end()) return false;
	return *it <= r;
}

void query(int x, int l, int r) {
	int ans = 0;
	Trie *p = root;
	for (int i = 30; i >= 0; --i) {
		int LOVE = (x >> i & 1) ^ 1;
		if (p->nxt[LOVE] == nullptr || !check(p->nxt[LOVE], l, r)) LOVE ^= 1;
		p = p->nxt[LOVE]; ans += LOVE << i;
	}
	cout << (ans ^ x) << '\n';
}

void dfs(int u) {
	tin[u] = ++timer;
	for (pair<int, int> x: adj[u]) {
		h[x.fi] = h[u] ^ x.se;
		dfs(x.fi);
	}
	tout[u] = timer;
}

int main() {
  	ios_base::sync_with_stdio(0);
  	cin.tie(0); cout.tie(0);

  	if (fopen(task".inp","r")) {
    	freopen(task".inp","r",stdin);
    	freopen(task".out","w",stdout);
  	}

	cin >> n;
	numNode = 1;
	for (int i = 0; i < n; ++i) {
		cin >> op >> a >> b; q[i] = {op, {a, b}};
		if (op == "Add") adj[a].push_back({++numNode, b});
	}
	dfs(1); numNode = 1;
	root = new Trie(); add(1);
	for (int i = 0; i < n; ++i) {
		if (q[i].fi == "Add") add(++numNode);
		else query(h[q[i].se.fi], tin[q[i].se.se], tout[q[i].se.se]);
	}
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:76:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:77:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 8 ms 13268 KB Output is correct
4 Correct 7 ms 13372 KB Output is correct
5 Correct 7 ms 12988 KB Output is correct
6 Correct 7 ms 13116 KB Output is correct
7 Correct 8 ms 13248 KB Output is correct
8 Correct 7 ms 13396 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13140 KB Output is correct
11 Correct 7 ms 13268 KB Output is correct
12 Correct 8 ms 13396 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 8 ms 13268 KB Output is correct
4 Correct 7 ms 13372 KB Output is correct
5 Correct 7 ms 12988 KB Output is correct
6 Correct 7 ms 13116 KB Output is correct
7 Correct 8 ms 13248 KB Output is correct
8 Correct 7 ms 13396 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13140 KB Output is correct
11 Correct 7 ms 13268 KB Output is correct
12 Correct 8 ms 13396 KB Output is correct
13 Correct 10 ms 14164 KB Output is correct
14 Correct 10 ms 15432 KB Output is correct
15 Correct 12 ms 16784 KB Output is correct
16 Correct 13 ms 17848 KB Output is correct
17 Correct 10 ms 14168 KB Output is correct
18 Correct 11 ms 15340 KB Output is correct
19 Correct 12 ms 16596 KB Output is correct
20 Correct 14 ms 17748 KB Output is correct
21 Correct 9 ms 14156 KB Output is correct
22 Correct 11 ms 15444 KB Output is correct
23 Correct 12 ms 16596 KB Output is correct
24 Correct 13 ms 17732 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 125488 KB Output is correct
2 Correct 934 ms 233748 KB Output is correct
3 Correct 1365 ms 334924 KB Output is correct
4 Correct 1731 ms 436780 KB Output is correct
5 Correct 606 ms 126052 KB Output is correct
6 Correct 1008 ms 229652 KB Output is correct
7 Correct 1469 ms 328724 KB Output is correct
8 Correct 1940 ms 427848 KB Output is correct
9 Correct 553 ms 125712 KB Output is correct
10 Correct 939 ms 230596 KB Output is correct
11 Correct 1398 ms 331236 KB Output is correct
12 Correct 1729 ms 430264 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 8 ms 13268 KB Output is correct
4 Correct 7 ms 13372 KB Output is correct
5 Correct 7 ms 12988 KB Output is correct
6 Correct 7 ms 13116 KB Output is correct
7 Correct 8 ms 13248 KB Output is correct
8 Correct 7 ms 13396 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 7 ms 13140 KB Output is correct
11 Correct 7 ms 13268 KB Output is correct
12 Correct 8 ms 13396 KB Output is correct
13 Correct 10 ms 14164 KB Output is correct
14 Correct 10 ms 15432 KB Output is correct
15 Correct 12 ms 16784 KB Output is correct
16 Correct 13 ms 17848 KB Output is correct
17 Correct 10 ms 14168 KB Output is correct
18 Correct 11 ms 15340 KB Output is correct
19 Correct 12 ms 16596 KB Output is correct
20 Correct 14 ms 17748 KB Output is correct
21 Correct 9 ms 14156 KB Output is correct
22 Correct 11 ms 15444 KB Output is correct
23 Correct 12 ms 16596 KB Output is correct
24 Correct 13 ms 17732 KB Output is correct
25 Correct 527 ms 125488 KB Output is correct
26 Correct 934 ms 233748 KB Output is correct
27 Correct 1365 ms 334924 KB Output is correct
28 Correct 1731 ms 436780 KB Output is correct
29 Correct 606 ms 126052 KB Output is correct
30 Correct 1008 ms 229652 KB Output is correct
31 Correct 1469 ms 328724 KB Output is correct
32 Correct 1940 ms 427848 KB Output is correct
33 Correct 553 ms 125712 KB Output is correct
34 Correct 939 ms 230596 KB Output is correct
35 Correct 1398 ms 331236 KB Output is correct
36 Correct 1729 ms 430264 KB Output is correct
37 Correct 1006 ms 129276 KB Output is correct
38 Correct 1434 ms 233804 KB Output is correct
39 Correct 1768 ms 337736 KB Output is correct
40 Correct 1930 ms 437272 KB Output is correct
41 Correct 1072 ms 126820 KB Output is correct
42 Correct 1499 ms 229576 KB Output is correct
43 Correct 1810 ms 328972 KB Output is correct
44 Correct 2113 ms 427388 KB Output is correct
45 Correct 1151 ms 126180 KB Output is correct
46 Correct 1589 ms 230580 KB Output is correct
47 Correct 1850 ms 330024 KB Output is correct
48 Correct 2017 ms 430048 KB Output is correct