oj.uz

Submission #235560

# Submission time Handle Problem Language Result Execution time Memory
235560 2020-05-28T14:24:01 Z doowey Klasika (COCI20_klasika) C++14
33 / 110
 2305 ms 524292 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)6e6 + 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 160 ms 286968 KB Output is correct
2 Correct 179 ms 286968 KB Output is correct
3 Correct 164 ms 287096 KB Output is correct
4 Correct 166 ms 287096 KB Output is correct
5 Correct 161 ms 287100 KB Output is correct
6 Correct 163 ms 287096 KB Output is correct
7 Correct 163 ms 287096 KB Output is correct
8 Correct 160 ms 287096 KB Output is correct
9 Correct 164 ms 286968 KB Output is correct
10 Correct 157 ms 287096 KB Output is correct
11 Correct 166 ms 287096 KB Output is correct
12 Correct 165 ms 287096 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 286968 KB Output is correct
2 Correct 179 ms 286968 KB Output is correct
3 Correct 164 ms 287096 KB Output is correct
4 Correct 166 ms 287096 KB Output is correct
5 Correct 161 ms 287100 KB Output is correct
6 Correct 163 ms 287096 KB Output is correct
7 Correct 163 ms 287096 KB Output is correct
8 Correct 160 ms 287096 KB Output is correct
9 Correct 164 ms 286968 KB Output is correct
10 Correct 157 ms 287096 KB Output is correct
11 Correct 166 ms 287096 KB Output is correct
12 Correct 165 ms 287096 KB Output is correct
13 Correct 165 ms 287736 KB Output is correct
14 Correct 166 ms 288376 KB Output is correct
15 Correct 177 ms 289016 KB Output is correct
16 Correct 179 ms 289656 KB Output is correct
17 Correct 161 ms 287608 KB Output is correct
18 Correct 162 ms 288252 KB Output is correct
19 Correct 166 ms 289016 KB Output is correct
20 Correct 168 ms 289528 KB Output is correct
21 Correct 177 ms 287608 KB Output is correct
22 Correct 163 ms 288248 KB Output is correct
23 Correct 164 ms 289016 KB Output is correct
24 Correct 175 ms 289528 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 358320 KB Output is correct
2 Correct 1686 ms 426700 KB Output is correct
3 Correct 2305 ms 490880 KB Output is correct
4 Runtime error 2214 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 286968 KB Output is correct
2 Correct 179 ms 286968 KB Output is correct
3 Correct 164 ms 287096 KB Output is correct
4 Correct 166 ms 287096 KB Output is correct
5 Correct 161 ms 287100 KB Output is correct
6 Correct 163 ms 287096 KB Output is correct
7 Correct 163 ms 287096 KB Output is correct
8 Correct 160 ms 287096 KB Output is correct
9 Correct 164 ms 286968 KB Output is correct
10 Correct 157 ms 287096 KB Output is correct
11 Correct 166 ms 287096 KB Output is correct
12 Correct 165 ms 287096 KB Output is correct
13 Correct 165 ms 287736 KB Output is correct
14 Correct 166 ms 288376 KB Output is correct
15 Correct 177 ms 289016 KB Output is correct
16 Correct 179 ms 289656 KB Output is correct
17 Correct 161 ms 287608 KB Output is correct
18 Correct 162 ms 288252 KB Output is correct
19 Correct 166 ms 289016 KB Output is correct
20 Correct 168 ms 289528 KB Output is correct
21 Correct 177 ms 287608 KB Output is correct
22 Correct 163 ms 288248 KB Output is correct
23 Correct 164 ms 289016 KB Output is correct
24 Correct 175 ms 289528 KB Output is correct
25 Correct 1022 ms 358320 KB Output is correct
26 Correct 1686 ms 426700 KB Output is correct
27 Correct 2305 ms 490880 KB Output is correct
28 Runtime error 2214 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -