oj.uz

Submission #492911

# Submission time Handle Problem Language Result Execution time Memory
492911 2021-12-09T17:29:04 Z pauloamed Klasika (COCI20_klasika) C++14
33 / 110
 294 ms 62696 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].size++;
    if(curr_bit == -1) return;
    if(curr_bit == 31) added.push_back(num);
    propagate_xor(curr_node, curr_bit);
 
    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
    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);
    // if(ans[t] == 1073617240){
    //   cout << a << " " << tries[x].query_max(a, t) << endl;
    // }
  }
}
 
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:185:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  185 |   for(auto [i, ab] : q){
      |            ^
klasika.cpp:186:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  186 |     auto [start, subtree] = ab;
      |          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26188 KB Output is correct
2 Correct 25 ms 26228 KB Output is correct
3 Correct 22 ms 26280 KB Output is correct
4 Correct 22 ms 26324 KB Output is correct
5 Correct 22 ms 26188 KB Output is correct
6 Correct 22 ms 26180 KB Output is correct
7 Correct 22 ms 26316 KB Output is correct
8 Correct 24 ms 26540 KB Output is correct
9 Correct 21 ms 26268 KB Output is correct
10 Correct 22 ms 26384 KB Output is correct
11 Correct 22 ms 26316 KB Output is correct
12 Correct 22 ms 26392 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26188 KB Output is correct
2 Correct 25 ms 26228 KB Output is correct
3 Correct 22 ms 26280 KB Output is correct
4 Correct 22 ms 26324 KB Output is correct
5 Correct 22 ms 26188 KB Output is correct
6 Correct 22 ms 26180 KB Output is correct
7 Correct 22 ms 26316 KB Output is correct
8 Correct 24 ms 26540 KB Output is correct
9 Correct 21 ms 26268 KB Output is correct
10 Correct 22 ms 26384 KB Output is correct
11 Correct 22 ms 26316 KB Output is correct
12 Correct 22 ms 26392 KB Output is correct
13 Correct 22 ms 26684 KB Output is correct
14 Correct 23 ms 27156 KB Output is correct
15 Correct 25 ms 27144 KB Output is correct
16 Correct 28 ms 27868 KB Output is correct
17 Correct 25 ms 27212 KB Output is correct
18 Correct 28 ms 28168 KB Output is correct
19 Correct 27 ms 29052 KB Output is correct
20 Correct 28 ms 29788 KB Output is correct
21 Correct 26 ms 26976 KB Output is correct
22 Correct 26 ms 27656 KB Output is correct
23 Correct 26 ms 28048 KB Output is correct
24 Correct 26 ms 28476 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26188 KB Output is correct
2 Correct 25 ms 26228 KB Output is correct
3 Correct 22 ms 26280 KB Output is correct
4 Correct 22 ms 26324 KB Output is correct
5 Correct 22 ms 26188 KB Output is correct
6 Correct 22 ms 26180 KB Output is correct
7 Correct 22 ms 26316 KB Output is correct
8 Correct 24 ms 26540 KB Output is correct
9 Correct 21 ms 26268 KB Output is correct
10 Correct 22 ms 26384 KB Output is correct
11 Correct 22 ms 26316 KB Output is correct
12 Correct 22 ms 26392 KB Output is correct
13 Correct 22 ms 26684 KB Output is correct
14 Correct 23 ms 27156 KB Output is correct
15 Correct 25 ms 27144 KB Output is correct
16 Correct 28 ms 27868 KB Output is correct
17 Correct 25 ms 27212 KB Output is correct
18 Correct 28 ms 28168 KB Output is correct
19 Correct 27 ms 29052 KB Output is correct
20 Correct 28 ms 29788 KB Output is correct
21 Correct 26 ms 26976 KB Output is correct
22 Correct 26 ms 27656 KB Output is correct
23 Correct 26 ms 28048 KB Output is correct
24 Correct 26 ms 28476 KB Output is correct
25 Incorrect 294 ms 62696 KB Output isn't correct
26 Halted 0 ms 0 KB -