Submission #500972

#TimeUsernameProblemLanguageResultExecution timeMemory
500972someoneKlasika (COCI20_klasika)C++14
110 / 110
666 ms245768 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 42, INF = 1e18 + 42, MOD = 1e9 + 7; struct Query { int a, t; }; struct Node { int id[2], mini; }; struct Trie { int sz = 0; vector<Query> q; vector<Node> node; Trie() { node.push_back({{-1, -1}, INF}); } void insert(int val, int t) { int a = 0; q.push_back({val, t}); for(int i = 29; i > -1; i--) { int b = min((val & (1 << i)), 1ll); if(node[a].id[b] == -1) { node[a].id[b] = ++sz; node.push_back({{-1, -1}, INF}); } a = node[a].id[b]; node[a].mini = min(node[a].mini, t); } } int getMax(int val, int t) { int ans = 0, a = 0; for(int i = 29; i > -1; i--) { ans <<= 1; int b = min((val & (1 << i)), 1ll); if(node[a].id[1 - b] != -1 && node[node[a].id[1 - b]].mini < t) { ans++; a = node[a].id[1 - b]; } else a = node[a].id[b]; } return ans; } }; vector<Query> q[N]; vector<int> adj[N]; int n, XOR[N], temps[N], ans[N]; Trie DFS(int i) { Trie act; act.insert(XOR[i], temps[i]); for(int j : adj[i]) { Trie child = DFS(j); if(child.q.size() > act.q.size()) swap(child, act); for(Query req : child.q) act.insert(req.a, req.t); } for(Query req : q[i]) ans[req.t] = act.getMax(XOR[req.a], req.t); return act; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int nb = 1; for(int i = 0; i < n; i++) ans[i] = -1; for(int i = 0; i < n; i++) { string str; int a, b; cin >> str >> a >> b; if(str[0] == 'A') { a--; temps[nb] = i; adj[a].push_back(nb); XOR[nb] = XOR[a] ^ b; nb++; } else { q[b-1].push_back({a-1, i}); } } DFS(0); for(int i = 0; i < n; i++) if(ans[i] != -1) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...