Submission #1319286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319286		sonarcht	Klasika (COCI20_klasika)	C++20	110 / 110	342 ms	123736 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(v) begin(v), end(v)
#define pll pair<ll, ll>
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll, ll>
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 2e5 + 6, B = 30, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans[N], a[N], pf[N], ti[N];
vector<pll> qry[N];

ll child[N*B][2], mn_ti[N*B], cur = 0;
void add(ll x, ll t) {
	ll u = 0;
	for (int j = 30; j >= 0; --j) {
		ll b = x >> j & 1;
		if (!child[u][b]) child[u][b] = ++cur;
		u = child[u][b];
		mn_ti[u] = min(mn_ti[u], t);
	}
}

ll search(ll x, ll t) {
	ll u = 0;
	ll ans = 0;
	for (int j = 30; j >= 0; --j) {
		ll b = x >> j & 1;
		if (child[u][!b] && mn_ti[child[u][!b]] <= t) {
			ans |= (1 << j);
			u = child[u][!b];
		} else u = child[u][b];
	}
	return ans;
}

void clear() {
	for (int i = 0; i <= cur; ++i) {
		child[i][0] = child[i][1] = 0;
		mn_ti[i] = inf;
	}
	cur = 0;
}

vll adj[N];
ll timer = 0, tin[N], tout[N], tour[N], sz[N], hvy[N];
void dfs(ll p, ll u) {
	tin[u] = ++timer;
	tour[timer] = u;
	sz[u] = 1;
	for (ll v : adj[u]) {
		if (v == p) continue;
		dfs(u, v);
		sz[u] += sz[v];
		if (sz[v] > sz[hvy[u]]) hvy[u] = v;
	}
	tout[u] = timer;
}

void sack(ll p, ll u, ll keep) {
	for (ll v : adj[u]) {
		if (v != p && v != hvy[u]) sack(u, v, 0);
	}
	if (hvy[u]) sack(u, hvy[u], 1);
	for (ll v : adj[u]) {
		if (v == p || v == hvy[u]) continue;
		for (int i = tin[v]; i <= tout[v]; ++i) add(pf[tour[i]], ti[tour[i]]);
	}
	add(pf[u], ti[u]);
	for (auto i : qry[u]) ans[i.se] = search(pf[i.fi], i.se);
	if (!keep) clear();
}
void solve() {
	cin >> q;
	n = 1;
	for (int i = 1; i <= q; ++i) {
		string tp;
		ll x, y;
		cin >> tp >> x >> y;
		if (tp == "Add") {
			adj[x].pb(++n);
			adj[n].pb(x);
			ti[n] = i;
			pf[n] = pf[x] ^ y;
		} else {
			qry[y].pb({x, i});
		}
	}
	fill(ans, ans+N, inf);
	fill(mn_ti, mn_ti + N*B, inf);
	dfs(-1, 1);
	sack(-1, 1, 1);
	for (int i = 1; i <= q; ++i) {
		if (ans[i] != inf) cout << ans[i] << endl;
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll tc = 1;
//	cin >> tc;
	while (tc--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:109:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
klasika.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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