oj.uz

Submission #492912

# Submission time Handle Problem Language Result Execution time Memory
492912 2021-12-09T17:32:38 Z Malheiros Klasika (COCI20_klasika) C++17
33 / 110
 315 ms 127028 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++;
    if(curr_bit == -1) return;
 
    nodes[curr_node].time_created = min(nodes[curr_node].time_created, time);
 
    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 500010
 
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 52 ms 63020 KB Output is correct
2 Correct 54 ms 63048 KB Output is correct
3 Correct 45 ms 63240 KB Output is correct
4 Correct 48 ms 63236 KB Output is correct
5 Correct 55 ms 63036 KB Output is correct
6 Correct 51 ms 63176 KB Output is correct
7 Correct 56 ms 63392 KB Output is correct
8 Correct 51 ms 63684 KB Output is correct
9 Correct 52 ms 63168 KB Output is correct
10 Correct 51 ms 63344 KB Output is correct
11 Correct 54 ms 63428 KB Output is correct
12 Correct 56 ms 63552 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63020 KB Output is correct
2 Correct 54 ms 63048 KB Output is correct
3 Correct 45 ms 63240 KB Output is correct
4 Correct 48 ms 63236 KB Output is correct
5 Correct 55 ms 63036 KB Output is correct
6 Correct 51 ms 63176 KB Output is correct
7 Correct 56 ms 63392 KB Output is correct
8 Correct 51 ms 63684 KB Output is correct
9 Correct 52 ms 63168 KB Output is correct
10 Correct 51 ms 63344 KB Output is correct
11 Correct 54 ms 63428 KB Output is correct
12 Correct 56 ms 63552 KB Output is correct
13 Correct 48 ms 63876 KB Output is correct
14 Correct 50 ms 64652 KB Output is correct
15 Correct 51 ms 64692 KB Output is correct
16 Correct 49 ms 66060 KB Output is correct
17 Correct 60 ms 64920 KB Output is correct
18 Correct 59 ms 66908 KB Output is correct
19 Correct 58 ms 68700 KB Output is correct
20 Correct 58 ms 69980 KB Output is correct
21 Correct 54 ms 64436 KB Output is correct
22 Correct 54 ms 65884 KB Output is correct
23 Correct 59 ms 66524 KB Output is correct
24 Correct 67 ms 67452 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 315 ms 127028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63020 KB Output is correct
2 Correct 54 ms 63048 KB Output is correct
3 Correct 45 ms 63240 KB Output is correct
4 Correct 48 ms 63236 KB Output is correct
5 Correct 55 ms 63036 KB Output is correct
6 Correct 51 ms 63176 KB Output is correct
7 Correct 56 ms 63392 KB Output is correct
8 Correct 51 ms 63684 KB Output is correct
9 Correct 52 ms 63168 KB Output is correct
10 Correct 51 ms 63344 KB Output is correct
11 Correct 54 ms 63428 KB Output is correct
12 Correct 56 ms 63552 KB Output is correct
13 Correct 48 ms 63876 KB Output is correct
14 Correct 50 ms 64652 KB Output is correct
15 Correct 51 ms 64692 KB Output is correct
16 Correct 49 ms 66060 KB Output is correct
17 Correct 60 ms 64920 KB Output is correct
18 Correct 59 ms 66908 KB Output is correct
19 Correct 58 ms 68700 KB Output is correct
20 Correct 58 ms 69980 KB Output is correct
21 Correct 54 ms 64436 KB Output is correct
22 Correct 54 ms 65884 KB Output is correct
23 Correct 59 ms 66524 KB Output is correct
24 Correct 67 ms 67452 KB Output is correct
25 Incorrect 315 ms 127028 KB Output isn't correct
26 Halted 0 ms 0 KB -