oj.uz

Submission #844700

# Submission time Handle Problem Language Result Execution time Memory
844700 2023-09-05T17:17:14 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 385 ms 118504 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

vector<pair<int, int> > adj[N];
vector<int> valxor(N);

struct node{
  int to[2];
  int cnt;
  node(){
    to[0] = to[1] = -1;
    cnt = 0;
  }
};

vector<node> t;

void add(int x){
  int v = 0;
  for(int i = 29; i >= 0; i--){
    int c = ((x & (1 << i)) > 0);
    if(t[v].to[c] == -1){
        t[v].to[c] = t.size();
        t.pb(node());
        t[v].cnt++;
    }
    v = t[v].to[c];
  }
  t[v].cnt++;
}

int solve(int v, int k, int tp, int val){
  if(tp < 0) return val;

  int mask = (k & (1 << tp) ? 0 : 1);

  if(t[v].to[mask] != -1){
    //cout<<"aldim "<<val<<" "<<tp<<" "<<t[v].to[mask]<<endl;
    return solve(t[v].to[mask], k, tp-1, val + (1 << tp));
  }
  else{
    //cout<<"alamadim "<<val + (1 << tp)<<endl;
    return solve(t[v].to[mask^1], k, tp-1, val);
  }
}

int32_t main(){
  //freopen("in.txt","r", stdin);
  t.pb(node());
  int q;
  cin>>q;
  int ncnt = 1;
  valxor[1] = 0;
  add(0);

  while(q--){
    string s;
    cin>>s;

    if(s == "Add"){
        int x, y;
        cin>>x>>y;
        ncnt++;
        adj[ncnt].pb({x, y});
        adj[x].pb({ncnt, y});
        valxor[ncnt] = (valxor[x] ^ y);
        add(valxor[ncnt]);
    }
    else{
        int a, b; // b == 1
        cin>>a>>b;
        int ans = 0;
        ans = solve(0, valxor[a], 29, 0);
        cout<<ans<<endl;
    }
  }
  return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 36100 KB Output is correct
2 Correct 361 ms 64672 KB Output is correct
3 Correct 328 ms 63672 KB Output is correct
4 Correct 296 ms 116784 KB Output is correct
5 Correct 377 ms 37052 KB Output is correct
6 Correct 372 ms 64312 KB Output is correct
7 Correct 358 ms 63448 KB Output is correct
8 Correct 322 ms 118504 KB Output is correct
9 Correct 385 ms 37836 KB Output is correct
10 Correct 373 ms 65476 KB Output is correct
11 Correct 317 ms 63396 KB Output is correct
12 Correct 292 ms 117928 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -