oj.uz

Submission #235564

# Submission time Handle Problem Language Result Execution time Memory
235564 2020-05-28T14:30:53 Z doowey Klasika (COCI20_klasika) C++14
110 / 110
 3488 ms 457948 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];
vector<set<int>> F;
int id;
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;
  F.push_back({});
  for(int j = 30 ; j >= 0 ; j -- ){
    if(trie[cur][0]==0){
      F.push_back({});
      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){
          F.push_back({});
          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 8 ms 5248 KB Output is correct
2 Correct 8 ms 5300 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5464 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5300 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5464 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct
13 Correct 13 ms 6588 KB Output is correct
14 Correct 14 ms 7992 KB Output is correct
15 Correct 16 ms 8500 KB Output is correct
16 Correct 19 ms 10932 KB Output is correct
17 Correct 12 ms 6588 KB Output is correct
18 Correct 14 ms 7992 KB Output is correct
19 Correct 15 ms 8372 KB Output is correct
20 Correct 17 ms 9396 KB Output is correct
21 Correct 12 ms 6588 KB Output is correct
22 Correct 14 ms 7992 KB Output is correct
23 Correct 16 ms 8372 KB Output is correct
24 Correct 17 ms 9268 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 115044 KB Output is correct
2 Correct 1681 ms 224328 KB Output is correct
3 Correct 2284 ms 285676 KB Output is correct
4 Correct 3077 ms 457936 KB Output is correct
5 Correct 975 ms 114728 KB Output is correct
6 Correct 1709 ms 223568 KB Output is correct
7 Correct 2344 ms 284628 KB Output is correct
8 Correct 3273 ms 450388 KB Output is correct
9 Correct 880 ms 114924 KB Output is correct
10 Correct 1648 ms 224392 KB Output is correct
11 Correct 2228 ms 286500 KB Output is correct
12 Correct 3116 ms 451876 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5300 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5464 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct
13 Correct 13 ms 6588 KB Output is correct
14 Correct 14 ms 7992 KB Output is correct
15 Correct 16 ms 8500 KB Output is correct
16 Correct 19 ms 10932 KB Output is correct
17 Correct 12 ms 6588 KB Output is correct
18 Correct 14 ms 7992 KB Output is correct
19 Correct 15 ms 8372 KB Output is correct
20 Correct 17 ms 9396 KB Output is correct
21 Correct 12 ms 6588 KB Output is correct
22 Correct 14 ms 7992 KB Output is correct
23 Correct 16 ms 8372 KB Output is correct
24 Correct 17 ms 9268 KB Output is correct
25 Correct 868 ms 115044 KB Output is correct
26 Correct 1681 ms 224328 KB Output is correct
27 Correct 2284 ms 285676 KB Output is correct
28 Correct 3077 ms 457936 KB Output is correct
29 Correct 975 ms 114728 KB Output is correct
30 Correct 1709 ms 223568 KB Output is correct
31 Correct 2344 ms 284628 KB Output is correct
32 Correct 3273 ms 450388 KB Output is correct
33 Correct 880 ms 114924 KB Output is correct
34 Correct 1648 ms 224392 KB Output is correct
35 Correct 2228 ms 286500 KB Output is correct
36 Correct 3116 ms 451876 KB Output is correct
37 Correct 1566 ms 117128 KB Output is correct
38 Correct 2210 ms 227512 KB Output is correct
39 Correct 3019 ms 291696 KB Output is correct
40 Correct 3141 ms 457948 KB Output is correct
41 Correct 1880 ms 115144 KB Output is correct
42 Correct 2560 ms 223940 KB Output is correct
43 Correct 2987 ms 284636 KB Output is correct
44 Correct 3405 ms 450792 KB Output is correct
45 Correct 2070 ms 115308 KB Output is correct
46 Correct 2728 ms 224568 KB Output is correct
47 Correct 3074 ms 285468 KB Output is correct
48 Correct 3488 ms 452216 KB Output is correct