This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |