oj.uz

Submission #492914

# Submission time Handle Problem Language Result Execution time Memory
492914 2021-12-09T17:38:36 Z pauloamed Klasika (COCI20_klasika) C++14
110 / 110
 1055 ms 521036 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;
 
    for(auto &y : added) y ^= x;
  }
 
  vector<int> added;
 
  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].time_created = min(nodes[curr_node].time_created, time);
    nodes[curr_node].size++;
    if(curr_bit == -1) return;
    if(curr_bit == 31) added.push_back(num);
    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
 
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);
  }
}
 
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];
    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:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |   for(auto [t, a] : queries[x]){
      |            ^
klasika.cpp: In function 'int main()':
klasika.cpp:182:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  182 |   for(auto [i, ab] : q){
      |            ^
klasika.cpp:183:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  183 |     auto [start, subtree] = ab;
      |          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26188 KB Output is correct
2 Correct 21 ms 26228 KB Output is correct
3 Correct 21 ms 26308 KB Output is correct
4 Correct 21 ms 26316 KB Output is correct
5 Correct 21 ms 26140 KB Output is correct
6 Correct 21 ms 26284 KB Output is correct
7 Correct 21 ms 26316 KB Output is correct
8 Correct 21 ms 26540 KB Output is correct
9 Correct 20 ms 26192 KB Output is correct
10 Correct 20 ms 26324 KB Output is correct
11 Correct 21 ms 26328 KB Output is correct
12 Correct 21 ms 26316 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26188 KB Output is correct
2 Correct 21 ms 26228 KB Output is correct
3 Correct 21 ms 26308 KB Output is correct
4 Correct 21 ms 26316 KB Output is correct
5 Correct 21 ms 26140 KB Output is correct
6 Correct 21 ms 26284 KB Output is correct
7 Correct 21 ms 26316 KB Output is correct
8 Correct 21 ms 26540 KB Output is correct
9 Correct 20 ms 26192 KB Output is correct
10 Correct 20 ms 26324 KB Output is correct
11 Correct 21 ms 26328 KB Output is correct
12 Correct 21 ms 26316 KB Output is correct
13 Correct 22 ms 26684 KB Output is correct
14 Correct 22 ms 27116 KB Output is correct
15 Correct 24 ms 27144 KB Output is correct
16 Correct 25 ms 27904 KB Output is correct
17 Correct 25 ms 27212 KB Output is correct
18 Correct 26 ms 28200 KB Output is correct
19 Correct 26 ms 28968 KB Output is correct
20 Correct 29 ms 29788 KB Output is correct
21 Correct 26 ms 26988 KB Output is correct
22 Correct 25 ms 27608 KB Output is correct
23 Correct 26 ms 28112 KB Output is correct
24 Correct 27 ms 28468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 59864 KB Output is correct
2 Correct 334 ms 88660 KB Output is correct
3 Correct 361 ms 95340 KB Output is correct
4 Correct 388 ms 142640 KB Output is correct
5 Correct 428 ms 142864 KB Output is correct
6 Correct 630 ms 273048 KB Output is correct
7 Correct 822 ms 366788 KB Output is correct
8 Correct 1048 ms 518240 KB Output is correct
9 Correct 341 ms 92224 KB Output is correct
10 Correct 438 ms 154768 KB Output is correct
11 Correct 517 ms 195584 KB Output is correct
12 Correct 606 ms 281560 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26188 KB Output is correct
2 Correct 21 ms 26228 KB Output is correct
3 Correct 21 ms 26308 KB Output is correct
4 Correct 21 ms 26316 KB Output is correct
5 Correct 21 ms 26140 KB Output is correct
6 Correct 21 ms 26284 KB Output is correct
7 Correct 21 ms 26316 KB Output is correct
8 Correct 21 ms 26540 KB Output is correct
9 Correct 20 ms 26192 KB Output is correct
10 Correct 20 ms 26324 KB Output is correct
11 Correct 21 ms 26328 KB Output is correct
12 Correct 21 ms 26316 KB Output is correct
13 Correct 22 ms 26684 KB Output is correct
14 Correct 22 ms 27116 KB Output is correct
15 Correct 24 ms 27144 KB Output is correct
16 Correct 25 ms 27904 KB Output is correct
17 Correct 25 ms 27212 KB Output is correct
18 Correct 26 ms 28200 KB Output is correct
19 Correct 26 ms 28968 KB Output is correct
20 Correct 29 ms 29788 KB Output is correct
21 Correct 26 ms 26988 KB Output is correct
22 Correct 25 ms 27608 KB Output is correct
23 Correct 26 ms 28112 KB Output is correct
24 Correct 27 ms 28468 KB Output is correct
25 Correct 296 ms 59864 KB Output is correct
26 Correct 334 ms 88660 KB Output is correct
27 Correct 361 ms 95340 KB Output is correct
28 Correct 388 ms 142640 KB Output is correct
29 Correct 428 ms 142864 KB Output is correct
30 Correct 630 ms 273048 KB Output is correct
31 Correct 822 ms 366788 KB Output is correct
32 Correct 1048 ms 518240 KB Output is correct
33 Correct 341 ms 92224 KB Output is correct
34 Correct 438 ms 154768 KB Output is correct
35 Correct 517 ms 195584 KB Output is correct
36 Correct 606 ms 281560 KB Output is correct
37 Correct 362 ms 63280 KB Output is correct
38 Correct 377 ms 89292 KB Output is correct
39 Correct 391 ms 95896 KB Output is correct
40 Correct 411 ms 143380 KB Output is correct
41 Correct 479 ms 151620 KB Output is correct
42 Correct 677 ms 277464 KB Output is correct
43 Correct 832 ms 360468 KB Output is correct
44 Correct 1055 ms 521036 KB Output is correct
45 Correct 375 ms 93312 KB Output is correct
46 Correct 464 ms 155344 KB Output is correct
47 Correct 548 ms 195516 KB Output is correct
48 Correct 601 ms 281928 KB Output is correct