Submission #674002

#	Time	Username	Problem	Language	Result	Execution time	Memory
674002		vjudge1	Klasika (COCI20_klasika)	C++14	0 / 110	219 ms	524288 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 = 6000005;
set<int> se[N];
int numNode = 1;
int h[N], timer;
int n, nxt[N][2];
string op; int a, b;
int tin[N], tout[N];
vector<pair<int, int>> adj[N];
pair<string, pair<int, int>> q[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 numNTrie = 0;

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

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

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

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);
  	}

	add(0);	
  	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;
  	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:67:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:68:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44