oj.uz

Submission #492915

# Submission time Handle Problem Language Result Execution time Memory
492915 2021-12-09T17:40:14 Z pauloamed Klasika (COCI20_klasika) C++14
110 / 110
 1000 ms 510992 KB 
#include<bits/stdc++.h>
using namespace std;
 
 
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
 
  void propagate_xor(int node, int curr_bit){
    if(get_bit(nodes[node].lazy, curr_bit)){
      swap(nodes[node].c[0], nodes[node].c[1]);
    }
 
    for(int i = 0; i < 2; ++i){
      if(nodes[node].c[i] != -1){
        nodes[nodes[node].c[i]].lazy ^= nodes[node].lazy; 
      }
    }
    nodes[node].lazy = 0;
  }
 
  void xor_all(int x){
    nodes[0].lazy ^= x;
  }
 
 
  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;
    propagate_xor(curr_node, curr_bit);
 
 
    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
    propagate_xor(curr_node, curr_bit);
 
    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
#define MAXLOG 20
 
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]] ^ xor_until[x], time_added[ver[it]]);
        }
      }
    }
  }
 
  tries[x].add(0, time_added[x]);
  for(auto [t, a] : queries[x]){
    ans[t] = a ^ tries[x].query_max(a, t);
  }
}
 
int main(){
  memset(ans, -1, sizeof ans);
 
  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] ^ xor_until[subtree];
    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";
  }
}

Compilation message

klasika.cpp: In function 'void solve(int)':
klasika.cpp:144:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |   for(auto [t, a] : queries[x]){
      |            ^
klasika.cpp: In function 'int main()':
klasika.cpp:172:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |   for(auto [i, ab] : q){
      |            ^
klasika.cpp:173:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |     auto [start, subtree] = ab;
      |          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 22 ms 21552 KB Output is correct
3 Correct 25 ms 21580 KB Output is correct
4 Correct 21 ms 21580 KB Output is correct
5 Correct 21 ms 21552 KB Output is correct
6 Correct 22 ms 21580 KB Output is correct
7 Correct 20 ms 21580 KB Output is correct
8 Correct 21 ms 21820 KB Output is correct
9 Correct 20 ms 21580 KB Output is correct
10 Correct 26 ms 21584 KB Output is correct
11 Correct 28 ms 21596 KB Output is correct
12 Correct 22 ms 21736 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 22 ms 21552 KB Output is correct
3 Correct 25 ms 21580 KB Output is correct
4 Correct 21 ms 21580 KB Output is correct
5 Correct 21 ms 21552 KB Output is correct
6 Correct 22 ms 21580 KB Output is correct
7 Correct 20 ms 21580 KB Output is correct
8 Correct 21 ms 21820 KB Output is correct
9 Correct 20 ms 21580 KB Output is correct
10 Correct 26 ms 21584 KB Output is correct
11 Correct 28 ms 21596 KB Output is correct
12 Correct 22 ms 21736 KB Output is correct
13 Correct 20 ms 22060 KB Output is correct
14 Correct 23 ms 22480 KB Output is correct
15 Correct 21 ms 22504 KB Output is correct
16 Correct 21 ms 23264 KB Output is correct
17 Correct 26 ms 22548 KB Output is correct
18 Correct 24 ms 23432 KB Output is correct
19 Correct 25 ms 24220 KB Output is correct
20 Correct 25 ms 25052 KB Output is correct
21 Correct 23 ms 22212 KB Output is correct
22 Correct 23 ms 22920 KB Output is correct
23 Correct 24 ms 23292 KB Output is correct
24 Correct 26 ms 23688 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 56888 KB Output is correct
2 Correct 338 ms 84608 KB Output is correct
3 Correct 350 ms 93000 KB Output is correct
4 Correct 381 ms 141864 KB Output is correct
5 Correct 415 ms 134952 KB Output is correct
6 Correct 608 ms 264140 KB Output is correct
7 Correct 776 ms 357988 KB Output is correct
8 Correct 986 ms 508676 KB Output is correct
9 Correct 333 ms 84944 KB Output is correct
10 Correct 477 ms 147884 KB Output is correct
11 Correct 514 ms 189044 KB Output is correct
12 Correct 632 ms 274904 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 22 ms 21552 KB Output is correct
3 Correct 25 ms 21580 KB Output is correct
4 Correct 21 ms 21580 KB Output is correct
5 Correct 21 ms 21552 KB Output is correct
6 Correct 22 ms 21580 KB Output is correct
7 Correct 20 ms 21580 KB Output is correct
8 Correct 21 ms 21820 KB Output is correct
9 Correct 20 ms 21580 KB Output is correct
10 Correct 26 ms 21584 KB Output is correct
11 Correct 28 ms 21596 KB Output is correct
12 Correct 22 ms 21736 KB Output is correct
13 Correct 20 ms 22060 KB Output is correct
14 Correct 23 ms 22480 KB Output is correct
15 Correct 21 ms 22504 KB Output is correct
16 Correct 21 ms 23264 KB Output is correct
17 Correct 26 ms 22548 KB Output is correct
18 Correct 24 ms 23432 KB Output is correct
19 Correct 25 ms 24220 KB Output is correct
20 Correct 25 ms 25052 KB Output is correct
21 Correct 23 ms 22212 KB Output is correct
22 Correct 23 ms 22920 KB Output is correct
23 Correct 24 ms 23292 KB Output is correct
24 Correct 26 ms 23688 KB Output is correct
25 Correct 331 ms 56888 KB Output is correct
26 Correct 338 ms 84608 KB Output is correct
27 Correct 350 ms 93000 KB Output is correct
28 Correct 381 ms 141864 KB Output is correct
29 Correct 415 ms 134952 KB Output is correct
30 Correct 608 ms 264140 KB Output is correct
31 Correct 776 ms 357988 KB Output is correct
32 Correct 986 ms 508676 KB Output is correct
33 Correct 333 ms 84944 KB Output is correct
34 Correct 477 ms 147884 KB Output is correct
35 Correct 514 ms 189044 KB Output is correct
36 Correct 632 ms 274904 KB Output is correct
37 Correct 337 ms 57724 KB Output is correct
38 Correct 393 ms 85620 KB Output is correct
39 Correct 394 ms 94136 KB Output is correct
40 Correct 393 ms 142588 KB Output is correct
41 Correct 450 ms 143792 KB Output is correct
42 Correct 619 ms 269156 KB Output is correct
43 Correct 778 ms 351424 KB Output is correct
44 Correct 1000 ms 510992 KB Output is correct
45 Correct 375 ms 86072 KB Output is correct
46 Correct 444 ms 148436 KB Output is correct
47 Correct 501 ms 188772 KB Output is correct
48 Correct 595 ms 275244 KB Output is correct