oj.uz

Submission #844442

# Submission time Handle Problem Language Result Execution time Memory
844442 2023-09-05T13:13:22 Z mychecksedad Klasika (COCI20_klasika) C++17
110 / 110
 1880 ms 276700 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18, KK = 30;


struct Query{
  int a, b, t, idx;
};

struct Node{
  Node *l, *r;
  int min_time;
  bool is;
  Node(){
    l = r = nullptr;
    min_time = MOD;
    is = 0;
  }
  void extend(){
    if(l == nullptr){
      l = new Node();
    }
    if(r == nullptr){
      r = new Node();
    }
  }
  void update(int new_time, int x, int dep){
    min_time = min(min_time, new_time);
    is = 1;
    if(dep == -1) return;
    extend();
    if(x&(1<<dep)){
      r->update(new_time, x, dep - 1);
    }else{
      l->update(new_time, x, dep - 1);
    }
  }
  int get(int val, int dep, int qt){
    extend();
    // cout << dep << ' ' << val << ' ' << min_time << ' ' << is << '\n';
    if((1<<dep)&val){
      if(l->is && l->min_time <= qt){
        return (1<<dep) + l->get(val, dep - 1, qt);
      }
      if(r->is && r->min_time <= qt)
        return r->get(val, dep - 1, qt);
      return 0;
    }
    if(r->is && r->min_time <= qt){
      return (1<<dep) + r->get(val, dep - 1, qt);
    }
    if(l->is && l->min_time <= qt)
      return l->get(val, dep - 1, qt);
    return 0;
  }
  void freeall(){
    if(l != nullptr){
      l->freeall();
    }
    if(r != nullptr){
      r->freeall();
    } 
    free(l);
    free(r);
  }
};

int q, ans[N], sz[N], n = 1, pref[N], bigxo[N];
vector<array<int, 3>> g[N];
vector<Query> Q[N];
vector<Node*> trie;
vector<pair<int, int>> values[N];

void pre(int v){
  sz[v] = 1;
  for(auto U: g[v]){
    int u = U[0];
    pref[u] = pref[v] ^ U[1];
    pre(u);
    sz[v] += sz[u];
  }
}

int calcc(int a, int b){
  return pref[a]^pref[b];
}
void dfs(int v, int w, int tm){
  int big = -1;
  for(auto U: g[v]){
    int u = U[0];
    dfs(u, U[1], U[2]);
    if(big == -1 || sz[u] > sz[big]) big = u;
  }
  if(big != -1){
    swap(trie[v], trie[big]);
    values[v].swap(values[big]);
  }else{
    trie[v] = new Node();
    trie[v]->is = 1;
  }
  for(auto U: g[v]){
    if(U[0] != big){
      for(auto x: values[U[0]]){
        trie[v]->update(x.second, x.first, KK);
        values[v].pb({x.first, x.second});
        // cout << (x.first ^ U[1] ^ bigxo[v]) << ' ' << v << '\n';
      }
      trie[U[0]]->freeall();
    }
  }
  // for(auto f: values[v]){
    // cout << f.first << ' ' << f.second << ' ' << v << '\n';
  // }
  values[v].pb({pref[v], tm});
  trie[v]->update(tm, pref[v], KK);
  for(auto qq: Q[v]){
    int xo = pref[qq.a];
    ans[qq.idx] = trie[v]->get(xo, KK, qq.t);
    // cout <<qq.t << ' ';
  }
  /*
  values[v].pb({w, tm});
  // cout << w << ' ' << tm << '\n';
  trie[v]->update(tm, w, KK);
  */
}

void solve(){
  cin >> q;
  int qq = 0;
  for(int i = 1; i <= q; ++i){
    string s; cin >> s;
    if(s == "Add"){
      int p, w; cin >> p >> w;
      g[p].pb({++n, w, i});
    }else{
      int a, b; cin >> a >> b;
      Q[b].pb({a, b, i, ++qq});
    }
  }
  pref[1] = 0;
  pre(1);
  trie.resize(n+1);
  dfs(1, 0, 0);

  for(int i = 1; i <= qq; ++i) cout << ans[i] << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:159:15: warning: unused variable 'aa' [-Wunused-variable]
  159 |   int tt = 1, aa;
      |               ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 16 ms 78600 KB Output is correct
3 Correct 19 ms 78792 KB Output is correct
4 Correct 17 ms 78812 KB Output is correct
5 Correct 17 ms 78684 KB Output is correct
6 Correct 18 ms 78684 KB Output is correct
7 Correct 17 ms 78684 KB Output is correct
8 Correct 17 ms 78680 KB Output is correct
9 Correct 17 ms 78560 KB Output is correct
10 Correct 17 ms 78732 KB Output is correct
11 Correct 17 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 16 ms 78600 KB Output is correct
3 Correct 19 ms 78792 KB Output is correct
4 Correct 17 ms 78812 KB Output is correct
5 Correct 17 ms 78684 KB Output is correct
6 Correct 18 ms 78684 KB Output is correct
7 Correct 17 ms 78684 KB Output is correct
8 Correct 17 ms 78680 KB Output is correct
9 Correct 17 ms 78560 KB Output is correct
10 Correct 17 ms 78732 KB Output is correct
11 Correct 17 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct
13 Correct 20 ms 79196 KB Output is correct
14 Correct 18 ms 79704 KB Output is correct
15 Correct 19 ms 80476 KB Output is correct
16 Correct 19 ms 80728 KB Output is correct
17 Correct 19 ms 79196 KB Output is correct
18 Correct 21 ms 79808 KB Output is correct
19 Correct 23 ms 80604 KB Output is correct
20 Correct 28 ms 81244 KB Output is correct
21 Correct 18 ms 79108 KB Output is correct
22 Correct 20 ms 79708 KB Output is correct
23 Correct 21 ms 80220 KB Output is correct
24 Correct 23 ms 80728 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 132960 KB Output is correct
2 Correct 257 ms 172948 KB Output is correct
3 Correct 299 ms 210452 KB Output is correct
4 Correct 373 ms 246636 KB Output is correct
5 Correct 583 ms 132768 KB Output is correct
6 Correct 996 ms 185800 KB Output is correct
7 Correct 1587 ms 219916 KB Output is correct
8 Correct 1880 ms 257192 KB Output is correct
9 Correct 372 ms 128116 KB Output is correct
10 Correct 491 ms 163628 KB Output is correct
11 Correct 608 ms 196372 KB Output is correct
12 Correct 720 ms 227540 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 78680 KB Output is correct
2 Correct 16 ms 78600 KB Output is correct
3 Correct 19 ms 78792 KB Output is correct
4 Correct 17 ms 78812 KB Output is correct
5 Correct 17 ms 78684 KB Output is correct
6 Correct 18 ms 78684 KB Output is correct
7 Correct 17 ms 78684 KB Output is correct
8 Correct 17 ms 78680 KB Output is correct
9 Correct 17 ms 78560 KB Output is correct
10 Correct 17 ms 78732 KB Output is correct
11 Correct 17 ms 78684 KB Output is correct
12 Correct 17 ms 78684 KB Output is correct
13 Correct 20 ms 79196 KB Output is correct
14 Correct 18 ms 79704 KB Output is correct
15 Correct 19 ms 80476 KB Output is correct
16 Correct 19 ms 80728 KB Output is correct
17 Correct 19 ms 79196 KB Output is correct
18 Correct 21 ms 79808 KB Output is correct
19 Correct 23 ms 80604 KB Output is correct
20 Correct 28 ms 81244 KB Output is correct
21 Correct 18 ms 79108 KB Output is correct
22 Correct 20 ms 79708 KB Output is correct
23 Correct 21 ms 80220 KB Output is correct
24 Correct 23 ms 80728 KB Output is correct
25 Correct 212 ms 132960 KB Output is correct
26 Correct 257 ms 172948 KB Output is correct
27 Correct 299 ms 210452 KB Output is correct
28 Correct 373 ms 246636 KB Output is correct
29 Correct 583 ms 132768 KB Output is correct
30 Correct 996 ms 185800 KB Output is correct
31 Correct 1587 ms 219916 KB Output is correct
32 Correct 1880 ms 257192 KB Output is correct
33 Correct 372 ms 128116 KB Output is correct
34 Correct 491 ms 163628 KB Output is correct
35 Correct 608 ms 196372 KB Output is correct
36 Correct 720 ms 227540 KB Output is correct
37 Correct 246 ms 134192 KB Output is correct
38 Correct 286 ms 174836 KB Output is correct
39 Correct 327 ms 212932 KB Output is correct
40 Correct 333 ms 247512 KB Output is correct
41 Correct 532 ms 141568 KB Output is correct
42 Correct 901 ms 187916 KB Output is correct
43 Correct 1294 ms 213352 KB Output is correct
44 Correct 1879 ms 276700 KB Output is correct
45 Correct 285 ms 127692 KB Output is correct
46 Correct 411 ms 163128 KB Output is correct
47 Correct 533 ms 195528 KB Output is correct
48 Correct 698 ms 227388 KB Output is correct