oj.uz

Submission #617074

# Submission time Handle Problem Language Result Execution time Memory
617074 2022-08-01T08:33:14 Z Bungmint Klasika (COCI20_klasika) C++17
110 / 110
 1238 ms 316244 KB 
// Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

#pragma region TEMPLATE

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down

#ifdef LOCAL
#include "miscellaneous/debug.h"
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda {
	template <typename Fun>
	struct y_combinator_result {
		Fun fun_;
		template <typename T>
		explicit constexpr y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		constexpr decltype(auto) operator()(Args &&...args) const {
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun) {
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

#pragma endregion TEMPLATE

// TODO: Test xor_max
/**
 * Description: Bit Trie supporting xor min and xor max queries
 * Source: Folklore, Benq
 * Verification: https://judge.yosupo.jp/problem/set_xor_min
 * Time complexity: O(MAXBIT) per insertion
 */

template <int SZ, int MAXBIT>
struct TrieBit {
    int nxt[SZ][2], num = 0;
	vi stck[SZ];
    TrieBit() { memset(nxt, 0, sizeof(nxt)); }
    void insert(ll x, int u) {
        int now = 0;
		stck[now].pb(sz(stck[now]) ? min(u, stck[now].back()) : u);
        for (int j = MAXBIT-1; j >= 0; j--) {
            bool fl = x>>j & 1;
            if (!nxt[now][fl]) nxt[now][fl] = ++num;
            now = nxt[now][fl];
			stck[now].pb(sz(stck[now]) ? min(u, stck[now].back()) : u);
        }
    }
	void erase(ll x) {
		int now = 0;
		stck[now].pop_back();;
        for (int j = MAXBIT-1; j >= 0; j--) {
            bool fl = x>>j & 1;
            if (!nxt[now][fl]) nxt[now][fl] = ++num;
            now = nxt[now][fl];
			stck[now].pop_back();
        }
	}
    ll query_xor_max(ll x, int time) {
        if (!sz(stck[0]) || stck[0].back() > time) return -1;
        int now = 0;
        for (int j = MAXBIT-1; j >= 0; j--) {
            bool fl = (x>>j & 1) ^ 1;
            if (!nxt[now][fl] || !sz(stck[nxt[now][fl]]) ||
			stck[nxt[now][fl]].back() > time) fl ^= 1;
            if (fl) x ^= 1<<j;
            now = nxt[now][fl];
        }
        return x;
    }
};
TrieBit<200010*30, 30> trie;

void solve() {
	int q; cin >> q;
	vector<vi> adj(1);
	vector<vector<ar<int, 3>>> queries(1);
	vpi ans;
	vi a(1);
	int num = 0;
	for (int i = 0; i < q; i++) {
		string s; cin >> s;
		if (s[0] == 'A') {
			int p, x; cin >> p >> x; p--;
			a.pb(x ^ a[p]);
			adj.pb({});
			num++;
			adj[p].pb(num);
			adj[num].pb(p);
			queries.pb({});
		}else{
			int u, v; cin >> u >> v;
			u--, v--;
			queries[v].pb({a[u], num, i});
		}
	}
	dbg(queries);
	vi s(num+1), tin(num+1), rev_tin(num+1);
	int ti{};
	auto init = y_combinator([&](auto self, int u = 0, int pu = -1) -> int {
		s[u] = 1;
		tin[u] = ti++;
		rev_tin[tin[u]] = u;
		for (auto &v : adj[u]) { 
			if (v == pu) continue;
			s[u] += self(v, u);
		}
		return s[u];
	});
	auto dfs = y_combinator([&](auto self, int u = 0, int pu = -1, bool big = 1) -> void {
		int big_ch = -1, mx = -1;
		for (auto &v : adj[u]) {
			if (v == pu) continue;
			if (ckmax(mx, s[v])) big_ch = v;
		}
		for (auto &v : adj[u]) {
			if (v != big_ch && v != pu)
				self(v, u, 0);
		}
		if (big_ch != -1) {
			self(big_ch, u, 1);
		}
		trie.insert(a[u], u);
		for (auto &v : adj[u]) {
			if (v == pu || v == big_ch) continue;
			for (int t = tin[v]; t < tin[v]+s[v]; t++) {
				trie.insert(a[rev_tin[t]], rev_tin[t]);
			}
		}
		dbg(u, queries[u]);
		for (auto &[aa, nn, id] : queries[u]) {
			ans.pb({id, trie.query_xor_max(aa, nn)});
		}
		if (!big) {
			for (int t = tin[u]; t < tin[u]+s[u]; t++) {
				trie.erase(a[rev_tin[t]]);
			}
		}
	});
	init();
	dfs();
	sort(all(ans));
	for (auto &[_, ret] : ans) cout << ret << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--) {
		solve();
	}
#ifdef LOCAL
	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

klasika.cpp:7: warning: ignoring '#pragma region TEMPLATE' [-Wunknown-pragmas]
    7 | #pragma region TEMPLATE
      | 
klasika.cpp:65: warning: ignoring '#pragma endregion TEMPLATE' [-Wunknown-pragmas]
   65 | #pragma endregion TEMPLATE
      | 
klasika.cpp: In function 'void solve()':
klasika.cpp:45:18: warning: statement has no effect [-Wunused-value]
   45 | #define dbg(...) 42
      |                  ^~
klasika.cpp:138:2: note: in expansion of macro 'dbg'
  138 |  dbg(queries);
      |  ^~~
klasika.cpp: In instantiation of 'solve()::<lambda(auto:24, int, int, bool)> [with auto:24 = std::reference_wrapper<const RecursiveLambda::y_combinator_result<solve()::<lambda(auto:24, int, int, bool)> > >]':
klasika.cpp:56:15:   required from 'constexpr decltype(auto) RecursiveLambda::y_combinator_result<Fun>::operator()(Args&& ...) const [with Args = {}; Fun = solve()::<lambda(auto:24, int, int, bool)>]'
klasika.cpp:182:6:   required from here
klasika.cpp:45:18: warning: statement has no effect [-Wunused-value]
   45 | #define dbg(...) 42
      |                  ^~
klasika.cpp:171:3: note: in expansion of macro 'dbg'
  171 |   dbg(u, queries[u]);
      |   ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 188152 KB Output is correct
2 Correct 87 ms 188208 KB Output is correct
3 Correct 86 ms 188268 KB Output is correct
4 Correct 88 ms 188228 KB Output is correct
5 Correct 87 ms 188124 KB Output is correct
6 Correct 90 ms 188312 KB Output is correct
7 Correct 94 ms 188236 KB Output is correct
8 Correct 85 ms 188248 KB Output is correct
9 Correct 94 ms 188236 KB Output is correct
10 Correct 84 ms 188152 KB Output is correct
11 Correct 87 ms 188256 KB Output is correct
12 Correct 87 ms 188332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 188152 KB Output is correct
2 Correct 87 ms 188208 KB Output is correct
3 Correct 86 ms 188268 KB Output is correct
4 Correct 88 ms 188228 KB Output is correct
5 Correct 87 ms 188124 KB Output is correct
6 Correct 90 ms 188312 KB Output is correct
7 Correct 94 ms 188236 KB Output is correct
8 Correct 85 ms 188248 KB Output is correct
9 Correct 94 ms 188236 KB Output is correct
10 Correct 84 ms 188152 KB Output is correct
11 Correct 87 ms 188256 KB Output is correct
12 Correct 87 ms 188332 KB Output is correct
13 Correct 88 ms 188636 KB Output is correct
14 Correct 88 ms 188940 KB Output is correct
15 Correct 90 ms 189428 KB Output is correct
16 Correct 90 ms 189708 KB Output is correct
17 Correct 102 ms 188600 KB Output is correct
18 Correct 92 ms 188900 KB Output is correct
19 Correct 92 ms 189212 KB Output is correct
20 Correct 100 ms 189504 KB Output is correct
21 Correct 91 ms 188548 KB Output is correct
22 Correct 93 ms 188876 KB Output is correct
23 Correct 92 ms 189248 KB Output is correct
24 Correct 108 ms 189468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 230580 KB Output is correct
2 Correct 449 ms 259376 KB Output is correct
3 Correct 540 ms 286256 KB Output is correct
4 Correct 708 ms 315972 KB Output is correct
5 Correct 475 ms 224824 KB Output is correct
6 Correct 699 ms 247680 KB Output is correct
7 Correct 972 ms 268616 KB Output is correct
8 Correct 1219 ms 292488 KB Output is correct
9 Correct 387 ms 225336 KB Output is correct
10 Correct 511 ms 249076 KB Output is correct
11 Correct 644 ms 271140 KB Output is correct
12 Correct 795 ms 295640 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 188152 KB Output is correct
2 Correct 87 ms 188208 KB Output is correct
3 Correct 86 ms 188268 KB Output is correct
4 Correct 88 ms 188228 KB Output is correct
5 Correct 87 ms 188124 KB Output is correct
6 Correct 90 ms 188312 KB Output is correct
7 Correct 94 ms 188236 KB Output is correct
8 Correct 85 ms 188248 KB Output is correct
9 Correct 94 ms 188236 KB Output is correct
10 Correct 84 ms 188152 KB Output is correct
11 Correct 87 ms 188256 KB Output is correct
12 Correct 87 ms 188332 KB Output is correct
13 Correct 88 ms 188636 KB Output is correct
14 Correct 88 ms 188940 KB Output is correct
15 Correct 90 ms 189428 KB Output is correct
16 Correct 90 ms 189708 KB Output is correct
17 Correct 102 ms 188600 KB Output is correct
18 Correct 92 ms 188900 KB Output is correct
19 Correct 92 ms 189212 KB Output is correct
20 Correct 100 ms 189504 KB Output is correct
21 Correct 91 ms 188548 KB Output is correct
22 Correct 93 ms 188876 KB Output is correct
23 Correct 92 ms 189248 KB Output is correct
24 Correct 108 ms 189468 KB Output is correct
25 Correct 356 ms 230580 KB Output is correct
26 Correct 449 ms 259376 KB Output is correct
27 Correct 540 ms 286256 KB Output is correct
28 Correct 708 ms 315972 KB Output is correct
29 Correct 475 ms 224824 KB Output is correct
30 Correct 699 ms 247680 KB Output is correct
31 Correct 972 ms 268616 KB Output is correct
32 Correct 1219 ms 292488 KB Output is correct
33 Correct 387 ms 225336 KB Output is correct
34 Correct 511 ms 249076 KB Output is correct
35 Correct 644 ms 271140 KB Output is correct
36 Correct 795 ms 295640 KB Output is correct
37 Correct 409 ms 230144 KB Output is correct
38 Correct 489 ms 259560 KB Output is correct
39 Correct 578 ms 287100 KB Output is correct
40 Correct 633 ms 316244 KB Output is correct
41 Correct 450 ms 224048 KB Output is correct
42 Correct 710 ms 247780 KB Output is correct
43 Correct 964 ms 268764 KB Output is correct
44 Correct 1238 ms 292488 KB Output is correct
45 Correct 370 ms 224620 KB Output is correct
46 Correct 530 ms 249348 KB Output is correct
47 Correct 656 ms 270844 KB Output is correct
48 Correct 824 ms 295684 KB Output is correct