oj.uz

Submission #235557

# Submission time Handle Problem Language Result Execution time Memory
235557 2020-05-28T14:23:27 Z doowey Klasika (COCI20_klasika) C++14
33 / 110
 813 ms 202628 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 100;
const int SZ = (int)6e5 + 100;
int trie[SZ][2];
int id;
set<int> F[SZ];
vector<int> T[N];
int tin[N], tout[N];
ll vl[N];
int tt;

int typ[N];
int ff[N];
int ss[N];
int ads[N];

void dfs(int u){
  tin[u] = ++tt;
  for(auto x : T[u])
    dfs(x);
  tout[u]=tt;
}

int main(){
  fastIO;
  int q;
  cin >> q;
  int idx = 1;
  string tiq;
  for(int i = 1; i <= q; i ++ ){
    cin >> tiq;
    if(tiq == "Add"){
      typ[i] = 0;
      idx ++ ;
      ads[i]=idx;
      cin >> ff[i] >> ss[i];
      T[ff[i]].push_back(idx);
      vl[idx] = (vl[ff[i]] ^ ss[i]);
    }
    else{
      typ[i] = 1;
      cin >> ff[i] >> ss[i];
    }
  }
  dfs(1);
  ll vv;
  int root;
  ll ans;
  int nn;
  int cld;
  int it;
  int cur, nx;
  int mx = 1;
  ll a2a;
  cur=0;
  for(int j = 30 ; j >= 0 ; j -- ){
    if(trie[cur][0]==0){
      trie[cur][0] = ++id;
    }
    cur=trie[cur][0];
    F[cur].insert(tin[1]);
  }
  for(int pp = 1; pp <= q; pp ++ ){
    if(typ[pp] == 0){
      cur = 0;
      mx ++ ;
      for(int j = 30 ; j >= 0 ; j -- ){
        if((vl[ads[pp]] & (1ll << j))){
          nx = 1;
        }
        else{
          nx = 0;
        }
        if(trie[cur][nx] == 0){
          trie[cur][nx] = ++id;
        }
        cur = trie[cur][nx];
        F[cur].insert(tin[ads[pp]]);
      }
    }
    else{
      vv = vl[ff[pp]];
      root = ss[pp];
      cur = 0;
      ans = 0;
      for(int j = 30; j >= 0; j -- ){
        if((vv & (1ll << j))){
          nx = 1;
        }
        else{
          nx = 0;
        }
        for(int d = 1; d >= 0 ; d -- ){
          nn = (nx ^ d);
          if(trie[cur][nn] == 0) continue;
          cld = trie[cur][nn];
          auto qq = F[cld].lower_bound(tin[root]);
          if(qq == F[cld].end() || (*qq)  > tout[root]){
            continue;
          }
          else{
            if(d) ans |= (1ll << j);
            cur = trie[cur][nn];
            break;
          }
        }
      }
      cout << ans << "\n";
    }
  }
  return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:63:7: warning: unused variable 'it' [-Wunused-variable]
   int it;
       ^~
klasika.cpp:66:6: warning: unused variable 'a2a' [-Wunused-variable]
   ll a2a;
      ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33408 KB Output is correct
3 Correct 23 ms 33408 KB Output is correct
4 Correct 23 ms 33536 KB Output is correct
5 Correct 24 ms 33408 KB Output is correct
6 Correct 23 ms 33408 KB Output is correct
7 Correct 23 ms 33408 KB Output is correct
8 Correct 23 ms 33536 KB Output is correct
9 Correct 23 ms 33280 KB Output is correct
10 Correct 23 ms 33408 KB Output is correct
11 Correct 23 ms 33536 KB Output is correct
12 Correct 23 ms 33536 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33408 KB Output is correct
3 Correct 23 ms 33408 KB Output is correct
4 Correct 23 ms 33536 KB Output is correct
5 Correct 24 ms 33408 KB Output is correct
6 Correct 23 ms 33408 KB Output is correct
7 Correct 23 ms 33408 KB Output is correct
8 Correct 23 ms 33536 KB Output is correct
9 Correct 23 ms 33280 KB Output is correct
10 Correct 23 ms 33408 KB Output is correct
11 Correct 23 ms 33536 KB Output is correct
12 Correct 23 ms 33536 KB Output is correct
13 Correct 25 ms 34176 KB Output is correct
14 Correct 26 ms 34688 KB Output is correct
15 Correct 28 ms 35456 KB Output is correct
16 Correct 30 ms 35968 KB Output is correct
17 Correct 26 ms 33920 KB Output is correct
18 Correct 28 ms 34680 KB Output is correct
19 Correct 29 ms 35328 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 26 ms 33920 KB Output is correct
22 Correct 30 ms 34688 KB Output is correct
23 Correct 29 ms 35320 KB Output is correct
24 Correct 30 ms 35968 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 813 ms 202628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33408 KB Output is correct
3 Correct 23 ms 33408 KB Output is correct
4 Correct 23 ms 33536 KB Output is correct
5 Correct 24 ms 33408 KB Output is correct
6 Correct 23 ms 33408 KB Output is correct
7 Correct 23 ms 33408 KB Output is correct
8 Correct 23 ms 33536 KB Output is correct
9 Correct 23 ms 33280 KB Output is correct
10 Correct 23 ms 33408 KB Output is correct
11 Correct 23 ms 33536 KB Output is correct
12 Correct 23 ms 33536 KB Output is correct
13 Correct 25 ms 34176 KB Output is correct
14 Correct 26 ms 34688 KB Output is correct
15 Correct 28 ms 35456 KB Output is correct
16 Correct 30 ms 35968 KB Output is correct
17 Correct 26 ms 33920 KB Output is correct
18 Correct 28 ms 34680 KB Output is correct
19 Correct 29 ms 35328 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 26 ms 33920 KB Output is correct
22 Correct 30 ms 34688 KB Output is correct
23 Correct 29 ms 35320 KB Output is correct
24 Correct 30 ms 35968 KB Output is correct
25 Runtime error 813 ms 202628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -