oj.uz

Submission #492796

# Submission time Handle Problem Language Result Execution time Memory
492796 2021-12-09T01:14:21 Z pauloamed Klasika (COCI20_klasika) C++14
33 / 110
 340 ms 56952 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;
    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
#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:147:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |   for(auto [t, a] : queries[x]){
      |            ^
klasika.cpp: In function 'int main()':
klasika.cpp:175:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  175 |   for(auto [i, ab] : q){
      |            ^
klasika.cpp:176:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |     auto [start, subtree] = ab;
      |          ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21452 KB Output is correct
2 Correct 24 ms 21564 KB Output is correct
3 Correct 22 ms 21540 KB Output is correct
4 Correct 21 ms 21532 KB Output is correct
5 Correct 20 ms 21440 KB Output is correct
6 Correct 19 ms 21568 KB Output is correct
7 Correct 20 ms 21648 KB Output is correct
8 Correct 20 ms 21836 KB Output is correct
9 Correct 18 ms 21580 KB Output is correct
10 Correct 21 ms 21648 KB Output is correct
11 Correct 20 ms 21720 KB Output is correct
12 Correct 19 ms 21708 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21452 KB Output is correct
2 Correct 24 ms 21564 KB Output is correct
3 Correct 22 ms 21540 KB Output is correct
4 Correct 21 ms 21532 KB Output is correct
5 Correct 20 ms 21440 KB Output is correct
6 Correct 19 ms 21568 KB Output is correct
7 Correct 20 ms 21648 KB Output is correct
8 Correct 20 ms 21836 KB Output is correct
9 Correct 18 ms 21580 KB Output is correct
10 Correct 21 ms 21648 KB Output is correct
11 Correct 20 ms 21720 KB Output is correct
12 Correct 19 ms 21708 KB Output is correct
13 Correct 21 ms 22056 KB Output is correct
14 Correct 27 ms 22412 KB Output is correct
15 Correct 24 ms 22540 KB Output is correct
16 Correct 22 ms 23280 KB Output is correct
17 Correct 22 ms 22480 KB Output is correct
18 Correct 23 ms 23472 KB Output is correct
19 Correct 24 ms 24336 KB Output is correct
20 Correct 25 ms 25112 KB Output is correct
21 Correct 21 ms 22212 KB Output is correct
22 Correct 23 ms 22952 KB Output is correct
23 Correct 24 ms 23324 KB Output is correct
24 Correct 24 ms 23800 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 56952 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 21452 KB Output is correct
2 Correct 24 ms 21564 KB Output is correct
3 Correct 22 ms 21540 KB Output is correct
4 Correct 21 ms 21532 KB Output is correct
5 Correct 20 ms 21440 KB Output is correct
6 Correct 19 ms 21568 KB Output is correct
7 Correct 20 ms 21648 KB Output is correct
8 Correct 20 ms 21836 KB Output is correct
9 Correct 18 ms 21580 KB Output is correct
10 Correct 21 ms 21648 KB Output is correct
11 Correct 20 ms 21720 KB Output is correct
12 Correct 19 ms 21708 KB Output is correct
13 Correct 21 ms 22056 KB Output is correct
14 Correct 27 ms 22412 KB Output is correct
15 Correct 24 ms 22540 KB Output is correct
16 Correct 22 ms 23280 KB Output is correct
17 Correct 22 ms 22480 KB Output is correct
18 Correct 23 ms 23472 KB Output is correct
19 Correct 24 ms 24336 KB Output is correct
20 Correct 25 ms 25112 KB Output is correct
21 Correct 21 ms 22212 KB Output is correct
22 Correct 23 ms 22952 KB Output is correct
23 Correct 24 ms 23324 KB Output is correct
24 Correct 24 ms 23800 KB Output is correct
25 Incorrect 340 ms 56952 KB Output isn't correct
26 Halted 0 ms 0 KB -