Submission #674007

#	Time	Username	Problem	Language	Result	Execution time	Memory
674007		chanhchuong123	Klasika (COCI20_klasika)	C++14	110 / 110	2113 ms	437272 KiB

klasika

#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 (stderr)

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 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44