oj.uz

Submission #492917

# Submission time Handle Problem Language Result Execution time Memory
492917 2021-12-09T17:42:00 Z Malheiros Klasika (COCI20_klasika) C++17
33 / 110
 593 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 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;
    xor_until[i]=0;
    w[i]=0;
  }
 
  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 70828 KB Output is correct
2 Correct 53 ms 70980 KB Output is correct
3 Correct 48 ms 71028 KB Output is correct
4 Correct 60 ms 71004 KB Output is correct
5 Correct 54 ms 70852 KB Output is correct
6 Correct 56 ms 70948 KB Output is correct
7 Correct 56 ms 71240 KB Output is correct
8 Correct 58 ms 71428 KB Output is correct
9 Correct 54 ms 70900 KB Output is correct
10 Correct 53 ms 71108 KB Output is correct
11 Correct 54 ms 71156 KB Output is correct
12 Correct 57 ms 71200 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70828 KB Output is correct
2 Correct 53 ms 70980 KB Output is correct
3 Correct 48 ms 71028 KB Output is correct
4 Correct 60 ms 71004 KB Output is correct
5 Correct 54 ms 70852 KB Output is correct
6 Correct 56 ms 70948 KB Output is correct
7 Correct 56 ms 71240 KB Output is correct
8 Correct 58 ms 71428 KB Output is correct
9 Correct 54 ms 70900 KB Output is correct
10 Correct 53 ms 71108 KB Output is correct
11 Correct 54 ms 71156 KB Output is correct
12 Correct 57 ms 71200 KB Output is correct
13 Correct 53 ms 71676 KB Output is correct
14 Correct 51 ms 72456 KB Output is correct
15 Correct 58 ms 72552 KB Output is correct
16 Correct 54 ms 73916 KB Output is correct
17 Correct 57 ms 72732 KB Output is correct
18 Correct 58 ms 74644 KB Output is correct
19 Correct 60 ms 76296 KB Output is correct
20 Correct 61 ms 77788 KB Output is correct
21 Correct 56 ms 72292 KB Output is correct
22 Correct 58 ms 73696 KB Output is correct
23 Correct 65 ms 74344 KB Output is correct
24 Correct 58 ms 75176 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 134112 KB Output is correct
2 Correct 366 ms 182032 KB Output is correct
3 Correct 386 ms 191232 KB Output is correct
4 Correct 455 ms 281608 KB Output is correct
5 Correct 469 ms 292412 KB Output is correct
6 Runtime error 593 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70828 KB Output is correct
2 Correct 53 ms 70980 KB Output is correct
3 Correct 48 ms 71028 KB Output is correct
4 Correct 60 ms 71004 KB Output is correct
5 Correct 54 ms 70852 KB Output is correct
6 Correct 56 ms 70948 KB Output is correct
7 Correct 56 ms 71240 KB Output is correct
8 Correct 58 ms 71428 KB Output is correct
9 Correct 54 ms 70900 KB Output is correct
10 Correct 53 ms 71108 KB Output is correct
11 Correct 54 ms 71156 KB Output is correct
12 Correct 57 ms 71200 KB Output is correct
13 Correct 53 ms 71676 KB Output is correct
14 Correct 51 ms 72456 KB Output is correct
15 Correct 58 ms 72552 KB Output is correct
16 Correct 54 ms 73916 KB Output is correct
17 Correct 57 ms 72732 KB Output is correct
18 Correct 58 ms 74644 KB Output is correct
19 Correct 60 ms 76296 KB Output is correct
20 Correct 61 ms 77788 KB Output is correct
21 Correct 56 ms 72292 KB Output is correct
22 Correct 58 ms 73696 KB Output is correct
23 Correct 65 ms 74344 KB Output is correct
24 Correct 58 ms 75176 KB Output is correct
25 Correct 323 ms 134112 KB Output is correct
26 Correct 366 ms 182032 KB Output is correct
27 Correct 386 ms 191232 KB Output is correct
28 Correct 455 ms 281608 KB Output is correct
29 Correct 469 ms 292412 KB Output is correct
30 Runtime error 593 ms 524292 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -