Submission #494023

#TimeUsernameProblemLanguageResultExecution timeMemory
494023VictorKlasika (COCI20_klasika)C++17
0 / 110
74 ms26044 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; const int MAXN = 200001; const int len = 31; int xor_root[MAXN + 5], euler_id[MAXN + 5], sub_size[MAXN + 5], n = 1, cnt = 0; struct Node { Node *zero = 0, *one = 0; set<int> nodes; int node_val = 0; void add(int val, int pos, int u) { nodes.insert(euler_id[u]); if (pos == -1) return; if (val & (1 << pos)) { assert(pos<20); if (one == 0) { one = new Node; one->node_val = node_val | (1 << pos); } one->add(val, pos - 1, u); } else { if (zero == 0) { zero = new Node; zero->node_val = node_val; } zero->add(val, pos - 1, u); } } int query(int val, int pos, int u) { if (pos == -1) return node_val; bool has_zero = 0; if (zero && *zero->nodes.lower_bound(euler_id[u]) < euler_id[u] + sub_size[u]) has_zero = 1; bool has_one = 0; if (one && *one->nodes.lower_bound(euler_id[u]) < euler_id[u] + sub_size[u]) has_one = 1; if (!has_zero) return one->query(val, pos - 1, u); if (!has_one) return zero->query(val, pos - 1, u); if (val & (1 << pos)) return zero->query(val, pos - 1, u); else return one->query(val, pos - 1, u); } }; vii graph[MAXN + 5]; void dfs(int u, int cur_xor) { sub_size[u] = 1; euler_id[u] = cnt++; xor_root[u] = cur_xor; trav(edge, graph[u]) { int v, w; tie(v, w) = edge; dfs(v, cur_xor ^ w); sub_size[u] += sub_size[v]; } } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); vector<iii> queries; int q; cin >> q; rep(i, 0, q) { string type; int a, b; cin >> type >> a >> b; queries.pb({type == "Add", {a, b}}); if (type == "Add") graph[a - 1].emplace_back(n++, b); } dfs(0, 0); Node trie; trie.add(0, 30, 0); cnt = 1; rep(i, 0, q) { int type; type = queries[i].first; if (type) { int u, w; tie(u, w) = queries[i].second; trie.add(xor_root[cnt], 30, cnt); ++cnt; } else { int u, v; tie(u, v) = queries[i].second; cout << (xor_root[u - 1] ^ trie.query(xor_root[u - 1], 30, v - 1)) << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...