oj.uz

Submission #492919

# Submission time Handle Problem Language Result Execution time Memory
492919 2021-12-09T17:42:51 Z Malheiros Klasika (COCI20_klasika) C++17
33 / 110
 699 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 

struct Node{
  int size, time_created, lazy;
  array<int,2> c;
  Node(int time, int _size = 0):
    size(_size), time_created(time), lazy(0), c({-1, -1}){}
};
 
struct PersMaxXORTrie{
  vector<Node> nodes;
  // root: nodes[0]
  // todos numeros sao armazenados em nos terminais
  // um no terminal pode manter mais de um numero


 
 
  PersMaxXORTrie(){
    nodes.push_back(Node(-1));
  }
 
  bool get_bit(int x, int i){
    return (x >> i) & 1;
  }
 
  void add(int num, int time, int curr_node = 0, int curr_bit = 31){
    nodes[curr_node].size++;
    
 
    nodes[curr_node].time_created = min(nodes[curr_node].time_created, time);
    if(curr_bit == -1) return;
    int b = get_bit(num, curr_bit);
    if(nodes[curr_node].c[b] == -1){
      nodes[curr_node].c[b] = nodes.size();
      nodes.push_back(Node(time));
    }
 
    add(num, time, nodes[curr_node].c[b], curr_bit - 1);
  }
 
  int query_max(int num, int max_perm_time, int curr_node = 0, int curr_bit = 31){
    // want to max (num ^ x)
    if(curr_bit == -1) return 0; // base recursion case
 
    assert(nodes[curr_node].size > 0); // cant enter an empty node
 
    int b = !get_bit(num, curr_bit); // target bit (maximize xor)
 
    if((nodes[curr_node].c[b] != -1) && (nodes[nodes[curr_node].c[b]].time_created <= max_perm_time)){
      return query_max(num, max_perm_time, nodes[curr_node].c[b], curr_bit - 1) + (b << curr_bit);
    }else{
      return query_max(num, max_perm_time, nodes[curr_node].c[!b], curr_bit - 1) + ((!b) << curr_bit);
    }
  }
 
};
 
#define MAXN 200010
 
vector<int> v[MAXN];
 
int dfs_time = 0;
int xor_until[MAXN];
int sz[MAXN];
int w[MAXN];
int beg[MAXN], en[MAXN], ver[MAXN];
int time_added[MAXN];
 
PersMaxXORTrie tries[MAXN];
 
void preprocess_dfs(int x, int p){
  // xor preffix
  xor_until[x] = xor_until[p] ^ w[x];
 
  // sack
  ver[dfs_time] = x;
  beg[x] = dfs_time++;
  sz[x] = 1;
 
  for(auto y : v[x]){
    if(y != p){
      preprocess_dfs(y, x);
      sz[x] += sz[y];
    }
  }
 
  // sack
  en[x] = dfs_time;
}
 
vector<pair<int,int>> queries[MAXN]; // time, val
int ans[MAXN];
 
void solve(int x){
  int heavy_child = -1;
  int max_size = -1;
 
  for (auto k : v[x]){
    if (sz[k] > max_size){
      max_size = sz[k];
      heavy_child = k;
    }
  }
 
  
  for (auto k : v[x]) solve(k);
 
  if(heavy_child != -1){
    swap(tries[x], tries[heavy_child]);
    // tries[x].xor_all(w[heavy_child]);
 
    for (auto k : v[x]){
      tries[k].nodes.clear();
      if (k != heavy_child){
        for(int it = beg[k]; it < en[k]; ++it){
          tries[x].add(xor_until[ver[it]], time_added[ver[it]]);
        }
      }
    }
  }
 
  tries[x].add(xor_until[x], time_added[x]);
 
  // cout << x << endl;
  // for(auto y : tries[x].added){
  //   cout << y << ", ";
  // }cout << endl;
 
  for(auto [t, a] : queries[x]){
    // cout << a << " " << tries[x].query_max(a, t) << endl;
    ans[t] = a ^ tries[x].query_max(a, t);
    // if(ans[t] == 1073617240){
    //   cout << a << " " << tries[x].query_max(a, t) << endl;
    // }
  }
}
 
signed main(){
  for(int i=0;i<MAXN;i++){
    ans[i]=-1;
  }
 
  int next_node = 2;
  int n; cin >> n;
  
  vector<pair<int,pair<int,int>>> q;
  for(int i = 0; i < n; ++i){
    string s; cin >> s;
    if(s[0] == 'A'){
      int par, weight; cin >> par >> weight;
      time_added[next_node] = i;
      w[next_node] = weight;
      v[par].push_back(next_node);
      next_node++;
    }else{
      int start, subtree; cin >> start >> subtree;
      q.push_back({i, {start, subtree}});
    }
  }
 
  preprocess_dfs(1, 0);
 
  for(auto [i, ab] : q){
    auto [start, subtree] = ab;
    int val = xor_until[start];
    queries[subtree].push_back({i, val});
  }
  q.clear();
  solve(1);
 
 
  for(int i = 0; i < MAXN; ++i){
    if(ans[i] != -1) cout << ans[i] << "\n";
  }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25444 KB Output is correct
2 Correct 24 ms 25452 KB Output is correct
3 Correct 19 ms 25672 KB Output is correct
4 Correct 19 ms 25680 KB Output is correct
5 Correct 21 ms 25536 KB Output is correct
6 Correct 21 ms 25632 KB Output is correct
7 Correct 23 ms 25804 KB Output is correct
8 Correct 22 ms 26132 KB Output is correct
9 Correct 23 ms 25488 KB Output is correct
10 Correct 21 ms 25804 KB Output is correct
11 Correct 22 ms 25880 KB Output is correct
12 Correct 21 ms 25820 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25444 KB Output is correct
2 Correct 24 ms 25452 KB Output is correct
3 Correct 19 ms 25672 KB Output is correct
4 Correct 19 ms 25680 KB Output is correct
5 Correct 21 ms 25536 KB Output is correct
6 Correct 21 ms 25632 KB Output is correct
7 Correct 23 ms 25804 KB Output is correct
8 Correct 22 ms 26132 KB Output is correct
9 Correct 23 ms 25488 KB Output is correct
10 Correct 21 ms 25804 KB Output is correct
11 Correct 22 ms 25880 KB Output is correct
12 Correct 21 ms 25820 KB Output is correct
13 Correct 22 ms 26284 KB Output is correct
14 Correct 22 ms 27060 KB Output is correct
15 Correct 23 ms 27180 KB Output is correct
16 Correct 22 ms 28480 KB Output is correct
17 Correct 26 ms 27320 KB Output is correct
18 Correct 27 ms 29316 KB Output is correct
19 Correct 27 ms 30920 KB Output is correct
20 Correct 30 ms 32368 KB Output is correct
21 Correct 23 ms 26872 KB Output is correct
22 Correct 25 ms 28352 KB Output is correct
23 Correct 28 ms 28980 KB Output is correct
24 Correct 28 ms 29792 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 89276 KB Output is correct
2 Correct 349 ms 137912 KB Output is correct
3 Correct 366 ms 147744 KB Output is correct
4 Correct 434 ms 238620 KB Output is correct
5 Correct 441 ms 247536 KB Output is correct
6 Correct 699 ms 504684 KB Output is correct
7 Runtime error 631 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25444 KB Output is correct
2 Correct 24 ms 25452 KB Output is correct
3 Correct 19 ms 25672 KB Output is correct
4 Correct 19 ms 25680 KB Output is correct
5 Correct 21 ms 25536 KB Output is correct
6 Correct 21 ms 25632 KB Output is correct
7 Correct 23 ms 25804 KB Output is correct
8 Correct 22 ms 26132 KB Output is correct
9 Correct 23 ms 25488 KB Output is correct
10 Correct 21 ms 25804 KB Output is correct
11 Correct 22 ms 25880 KB Output is correct
12 Correct 21 ms 25820 KB Output is correct
13 Correct 22 ms 26284 KB Output is correct
14 Correct 22 ms 27060 KB Output is correct
15 Correct 23 ms 27180 KB Output is correct
16 Correct 22 ms 28480 KB Output is correct
17 Correct 26 ms 27320 KB Output is correct
18 Correct 27 ms 29316 KB Output is correct
19 Correct 27 ms 30920 KB Output is correct
20 Correct 30 ms 32368 KB Output is correct
21 Correct 23 ms 26872 KB Output is correct
22 Correct 25 ms 28352 KB Output is correct
23 Correct 28 ms 28980 KB Output is correct
24 Correct 28 ms 29792 KB Output is correct
25 Correct 288 ms 89276 KB Output is correct
26 Correct 349 ms 137912 KB Output is correct
27 Correct 366 ms 147744 KB Output is correct
28 Correct 434 ms 238620 KB Output is correct
29 Correct 441 ms 247536 KB Output is correct
30 Correct 699 ms 504684 KB Output is correct
31 Runtime error 631 ms 524292 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -