oj.uz

Submission #844377

# Submission time Handle Problem Language Result Execution time Memory
844377 2023-09-05T12:48:48 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 460 ms 346864 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;
  }
};

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;
  bigxo[v] = 0;
  for(auto U: g[v]){
    int u = U[0];
    dfs(u, U[1], U[2]);
    if(big == -1 || sz[u] > sz[big]) big = u, bigxo[v] = bigxo[u]^U[1];
  }
  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 ^ U[1] ^ bigxo[v], KK);
        values[v].pb({x.first ^ U[1] ^ bigxo[v], x.second});
        // cout << (x.first ^ U[1] ^ bigxo[v]) << ' ' << v << '\n';
      }
    }
  }
  // for(auto f: values[v]){
    // cout << f.first << ' ' << f.second << ' ' << v << '\n';
  // }
  values[v].pb({bigxo[v], tm});
  trie[v]->update(tm, bigxo[v], KK);
  for(auto qq: Q[v]){
    int xo = calcc(v, qq.a);
    ans[qq.idx] = trie[v]->get(xo ^ bigxo[v], 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:149:15: warning: unused variable 'aa' [-Wunused-variable]
  149 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 78520 KB Output is correct
2 Correct 16 ms 78680 KB Output is correct
3 Correct 16 ms 78680 KB Output is correct
4 Correct 16 ms 78680 KB Output is correct
5 Incorrect 17 ms 78680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 78520 KB Output is correct
2 Correct 16 ms 78680 KB Output is correct
3 Correct 16 ms 78680 KB Output is correct
4 Correct 16 ms 78680 KB Output is correct
5 Incorrect 17 ms 78680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 132104 KB Output is correct
2 Correct 259 ms 172732 KB Output is correct
3 Correct 310 ms 210412 KB Output is correct
4 Correct 321 ms 246648 KB Output is correct
5 Incorrect 460 ms 346864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 78520 KB Output is correct
2 Correct 16 ms 78680 KB Output is correct
3 Correct 16 ms 78680 KB Output is correct
4 Correct 16 ms 78680 KB Output is correct
5 Incorrect 17 ms 78680 KB Output isn't correct
6 Halted 0 ms 0 KB -