// Aber der schlimmste Fiend, dem du begegnen kannst, wirst du immer dir selber sein
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define int long long int
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define rev reverse
#define all(x) x.begin(),x.end()
#define acc accumulate
#define sz size()
#define MOD 1000000007
#define rall(x) x.rbegin(),x.rend()
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const int N = 2e5 + 5;
struct node{
node *L = NULL, *R = NULL;
};
struct trie{
node root;
void insert(node *cur, int len, int x){
if(len == -1) return;
int bit = (x >> len) & 1;
if(bit && cur->L == NULL){
cur->L = new node;
}
if(!bit && cur->R == NULL){
cur->R = new node;
}
if(bit){
insert(cur->L, len-1, x);
}
else{
insert(cur->R, len-1, x);
}
}
int find(node *cur, int len, int x){
if(len == -1){
return 0;
}
int bit = (x >> len) & 1;
if(bit && cur->R != NULL){
return find(cur->R, len-1, x) + (1 << len);
}
if(!bit && cur->L != NULL){
return find(cur->L, len-1, x) + (1 << len);
}
return find(((cur->L == NULL) ? cur->R : cur->L), len-1, x);
}
};
vector<pair<int, int> > adj[N];
int gir[N], cik[N], ti = 1;
void dfs(int node, int parent){
gir[node] = ti++;
for(int i = 0; i < adj[node].sz; i++){
if(adj[node][i].ff != parent){
dfs(adj[node][i].ff, node);
}
}
cik[node] = ti-1;
}
trie seg[4*N];
void push(int i, int l, int r, int p, int x){
if(l > p || r < p){
return;
}
if(l == r){
seg[i].insert(&seg[i].root, 30, x);
return;
}
int m = (l + r) / 2;
push(i*2, l, m, p, x);
push(i*2+1, m+1, r, p, x);
seg[i].insert(&seg[i].root, 30, x);
}
int find_range(int i, int l, int r, int ql, int qr, int x){
if(l > qr || r < ql){
return 0;
}
if(l >= ql && r <= qr){
if(seg[i].root.L != NULL || seg[i].root.R != NULL){
return seg[i].find(&seg[i].root, 30, x);
}
return 0;
}
int m = (l + r) / 2;
return max(find_range(i*2, l, m, ql, qr, x), find_range(i*2+1, m+1, r, ql, qr, x));
}
inline void solve(){
int n;
cin >> n;
pair<string, pair<int, int> > a[n];
vector<int> ans;
for(int i = 0; i < n; i++){
cin >> a[i].ff >> a[i].ss.ff >> a[i].ss.ss;
}
int node_count = 1;
for(int i = 0; i < n; i++){
if(a[i].ff == "Add"){
node_count++;
adj[a[i].ss.ff].pb({node_count, a[i].ss.ss});
adj[node_count].pb({a[i].ss.ff, a[i].ss.ff});
}
}
dfs(1, 1);
//for(int i = 1; i <= node_count; i++){
//cout << gir[i] << " " << cik[i] << endl;
//}
int xor_value[node_count+1];
xor_value[1] = 0;
node_count = 1;
push(1, 1, cik[1], gir[1], 0);
for(int i = 0; i < n; i++){
if(a[i].ff == "Add"){
node_count++;
xor_value[node_count] = xor_value[a[i].ss.ff] ^ a[i].ss.ss;
push(1, 1, cik[1], gir[node_count], xor_value[node_count]);
}
else{
ans.pb(find_range(1, 1, cik[1], gir[a[i].ss.ss], cik[a[i].ss.ss], xor_value[a[i].ss.ff]));
}
}
for(int i = 0; i < ans.sz; i++){
int x;
cin >> x;
if(x != ans[i]){
for(int i = 1; i <= 3; i++){
cout << xor_value[i] << " " << gir[i] << " " << cik[i] << endl;
}
cout << ans[i] << " " << x << endl;
cout << "NO" << endl;
return;
}
}
//for(int i = 1; i <= node_count; i++){
//cout << xor_value[i] << " ";
//}
}
int32_t main(){
fast_io
int t;
t = 1;
while(t--) solve();
}
Compilation message
klasika.cpp: In function 'void dfs(long long int, long long int)':
klasika.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < adj[node].sz; i++){
| ^
klasika.cpp: In function 'void solve()':
klasika.cpp:127:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; i < ans.sz; i++){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
671 ms |
502064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
