oj.uz

Submission #492916

# Submission time Handle Problem Language Result Execution time Memory
492916 2021-12-09T17:41:32 Z pauloamed Klasika (COCI20_klasika) C++14
110 / 110
 960 ms 511048 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 SemiPersMaxXORTrie{
  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;
  }
 
 
  SemiPersMaxXORTrie(){
    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];
 
SemiPersMaxXORTrie 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 18 ms 21460 KB Output is correct
2 Correct 19 ms 21560 KB Output is correct
3 Correct 20 ms 21580 KB Output is correct
4 Correct 19 ms 21576 KB Output is correct
5 Correct 19 ms 21448 KB Output is correct
6 Correct 19 ms 21616 KB Output is correct
7 Correct 19 ms 21580 KB Output is correct
8 Correct 20 ms 21856 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21580 KB Output is correct
11 Correct 19 ms 21588 KB Output is correct
12 Correct 19 ms 21676 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21460 KB Output is correct
2 Correct 19 ms 21560 KB Output is correct
3 Correct 20 ms 21580 KB Output is correct
4 Correct 19 ms 21576 KB Output is correct
5 Correct 19 ms 21448 KB Output is correct
6 Correct 19 ms 21616 KB Output is correct
7 Correct 19 ms 21580 KB Output is correct
8 Correct 20 ms 21856 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21580 KB Output is correct
11 Correct 19 ms 21588 KB Output is correct
12 Correct 19 ms 21676 KB Output is correct
13 Correct 22 ms 21952 KB Output is correct
14 Correct 21 ms 22436 KB Output is correct
15 Correct 23 ms 22448 KB Output is correct
16 Correct 21 ms 23268 KB Output is correct
17 Correct 22 ms 22560 KB Output is correct
18 Correct 22 ms 23476 KB Output is correct
19 Correct 24 ms 24232 KB Output is correct
20 Correct 27 ms 25072 KB Output is correct
21 Correct 23 ms 22212 KB Output is correct
22 Correct 22 ms 22996 KB Output is correct
23 Correct 24 ms 23268 KB Output is correct
24 Correct 24 ms 23780 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 56856 KB Output is correct
2 Correct 317 ms 84632 KB Output is correct
3 Correct 341 ms 92896 KB Output is correct
4 Correct 386 ms 141812 KB Output is correct
5 Correct 396 ms 134912 KB Output is correct
6 Correct 587 ms 264180 KB Output is correct
7 Correct 764 ms 358080 KB Output is correct
8 Correct 951 ms 508804 KB Output is correct
9 Correct 332 ms 84976 KB Output is correct
10 Correct 397 ms 147860 KB Output is correct
11 Correct 480 ms 188868 KB Output is correct
12 Correct 566 ms 274772 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21460 KB Output is correct
2 Correct 19 ms 21560 KB Output is correct
3 Correct 20 ms 21580 KB Output is correct
4 Correct 19 ms 21576 KB Output is correct
5 Correct 19 ms 21448 KB Output is correct
6 Correct 19 ms 21616 KB Output is correct
7 Correct 19 ms 21580 KB Output is correct
8 Correct 20 ms 21856 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21580 KB Output is correct
11 Correct 19 ms 21588 KB Output is correct
12 Correct 19 ms 21676 KB Output is correct
13 Correct 22 ms 21952 KB Output is correct
14 Correct 21 ms 22436 KB Output is correct
15 Correct 23 ms 22448 KB Output is correct
16 Correct 21 ms 23268 KB Output is correct
17 Correct 22 ms 22560 KB Output is correct
18 Correct 22 ms 23476 KB Output is correct
19 Correct 24 ms 24232 KB Output is correct
20 Correct 27 ms 25072 KB Output is correct
21 Correct 23 ms 22212 KB Output is correct
22 Correct 22 ms 22996 KB Output is correct
23 Correct 24 ms 23268 KB Output is correct
24 Correct 24 ms 23780 KB Output is correct
25 Correct 305 ms 56856 KB Output is correct
26 Correct 317 ms 84632 KB Output is correct
27 Correct 341 ms 92896 KB Output is correct
28 Correct 386 ms 141812 KB Output is correct
29 Correct 396 ms 134912 KB Output is correct
30 Correct 587 ms 264180 KB Output is correct
31 Correct 764 ms 358080 KB Output is correct
32 Correct 951 ms 508804 KB Output is correct
33 Correct 332 ms 84976 KB Output is correct
34 Correct 397 ms 147860 KB Output is correct
35 Correct 480 ms 188868 KB Output is correct
36 Correct 566 ms 274772 KB Output is correct
37 Correct 324 ms 57828 KB Output is correct
38 Correct 374 ms 85544 KB Output is correct
39 Correct 378 ms 94156 KB Output is correct
40 Correct 445 ms 142524 KB Output is correct
41 Correct 414 ms 143800 KB Output is correct
42 Correct 598 ms 269188 KB Output is correct
43 Correct 742 ms 351592 KB Output is correct
44 Correct 960 ms 511048 KB Output is correct
45 Correct 336 ms 86196 KB Output is correct
46 Correct 416 ms 148360 KB Output is correct
47 Correct 553 ms 188832 KB Output is correct
48 Correct 550 ms 275300 KB Output is correct