oj.uz

Submission #235554

# Submission time Handle Problem Language Result Execution time Memory
235554 2020-05-28T14:04:37 Z doowey Klasika (COCI20_klasika) C++14
33 / 110
 3914 ms 204972 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;
  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 = 1; j <= mx; j ++ ){
        if(tin[j] >= tin[root] && tout[j] <= tout[root])
          ans = max(ans, (vv ^ vl[j]));
      }
      /*
      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:61:7: warning: unused variable 'nn' [-Wunused-variable]
   int nn;
       ^~
klasika.cpp:62:7: warning: unused variable 'cld' [-Wunused-variable]
   int cld;
       ^~~
klasika.cpp:63:7: warning: unused variable 'it' [-Wunused-variable]
   int it;
       ^~

Subtask #1
11.0 / 11.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33408 KB Output is correct
2 Correct 24 ms 33408 KB Output is correct
3 Correct 24 ms 33408 KB Output is correct
4 Correct 24 ms 33536 KB Output is correct
5 Correct 24 ms 33400 KB Output is correct
6 Correct 24 ms 33408 KB Output is correct
7 Correct 24 ms 33408 KB Output is correct
8 Correct 25 ms 33536 KB Output is correct
9 Correct 25 ms 33272 KB Output is correct
10 Correct 24 ms 33408 KB Output is correct
11 Correct 23 ms 33408 KB Output is correct
12 Correct 24 ms 33536 KB Output is correct
13 Correct 32 ms 34148 KB Output is correct
14 Correct 30 ms 34688 KB Output is correct
15 Correct 28 ms 35456 KB Output is correct
16 Correct 30 ms 36096 KB Output is correct
17 Correct 27 ms 34048 KB Output is correct
18 Correct 28 ms 34688 KB Output is correct
19 Correct 31 ms 35328 KB Output is correct
20 Correct 31 ms 35968 KB Output is correct
21 Correct 27 ms 34048 KB Output is correct
22 Correct 28 ms 34688 KB Output is correct
23 Correct 29 ms 35328 KB Output is correct
24 Correct 33 ms 35968 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 3914 ms 204972 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 24 ms 33408 KB Output is correct
2 Correct 24 ms 33408 KB Output is correct
3 Correct 24 ms 33408 KB Output is correct
4 Correct 24 ms 33536 KB Output is correct
5 Correct 24 ms 33400 KB Output is correct
6 Correct 24 ms 33408 KB Output is correct
7 Correct 24 ms 33408 KB Output is correct
8 Correct 25 ms 33536 KB Output is correct
9 Correct 25 ms 33272 KB Output is correct
10 Correct 24 ms 33408 KB Output is correct
11 Correct 23 ms 33408 KB Output is correct
12 Correct 24 ms 33536 KB Output is correct
13 Correct 32 ms 34148 KB Output is correct
14 Correct 30 ms 34688 KB Output is correct
15 Correct 28 ms 35456 KB Output is correct
16 Correct 30 ms 36096 KB Output is correct
17 Correct 27 ms 34048 KB Output is correct
18 Correct 28 ms 34688 KB Output is correct
19 Correct 31 ms 35328 KB Output is correct
20 Correct 31 ms 35968 KB Output is correct
21 Correct 27 ms 34048 KB Output is correct
22 Correct 28 ms 34688 KB Output is correct
23 Correct 29 ms 35328 KB Output is correct
24 Correct 33 ms 35968 KB Output is correct
25 Runtime error 3914 ms 204972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -