oj.uz

답안 #492918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492918 2021-12-09T17:42:32 Z pauloamed Klasika (COCI20_klasika) C++14
110 / 110
 960 ms 510964 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 LazySemiPersMaxXORTrie{
  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;
  }
 
 
  LazySemiPersMaxXORTrie(){
    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];
 
LazySemiPersMaxXORTrie 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

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 19 ms 21452 KB Output is correct
3 Correct 19 ms 21612 KB Output is correct
4 Correct 18 ms 21580 KB Output is correct
5 Correct 19 ms 21524 KB Output is correct
6 Correct 23 ms 21616 KB Output is correct
7 Correct 19 ms 21596 KB Output is correct
8 Correct 19 ms 21832 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21696 KB Output is correct
11 Correct 19 ms 21708 KB Output is correct
12 Correct 19 ms 21632 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 19 ms 21452 KB Output is correct
3 Correct 19 ms 21612 KB Output is correct
4 Correct 18 ms 21580 KB Output is correct
5 Correct 19 ms 21524 KB Output is correct
6 Correct 23 ms 21616 KB Output is correct
7 Correct 19 ms 21596 KB Output is correct
8 Correct 19 ms 21832 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21696 KB Output is correct
11 Correct 19 ms 21708 KB Output is correct
12 Correct 19 ms 21632 KB Output is correct
13 Correct 19 ms 22060 KB Output is correct
14 Correct 19 ms 22456 KB Output is correct
15 Correct 20 ms 22536 KB Output is correct
16 Correct 20 ms 23204 KB Output is correct
17 Correct 22 ms 22560 KB Output is correct
18 Correct 28 ms 23476 KB Output is correct
19 Correct 25 ms 24280 KB Output is correct
20 Correct 26 ms 25096 KB Output is correct
21 Correct 22 ms 22212 KB Output is correct
22 Correct 23 ms 22944 KB Output is correct
23 Correct 23 ms 23336 KB Output is correct
24 Correct 25 ms 23688 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 56808 KB Output is correct
2 Correct 329 ms 84500 KB Output is correct
3 Correct 350 ms 92876 KB Output is correct
4 Correct 408 ms 141900 KB Output is correct
5 Correct 411 ms 134840 KB Output is correct
6 Correct 583 ms 264160 KB Output is correct
7 Correct 744 ms 357924 KB Output is correct
8 Correct 937 ms 508536 KB Output is correct
9 Correct 323 ms 84940 KB Output is correct
10 Correct 407 ms 147996 KB Output is correct
11 Correct 483 ms 189000 KB Output is correct
12 Correct 559 ms 274760 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 21452 KB Output is correct
2 Correct 19 ms 21452 KB Output is correct
3 Correct 19 ms 21612 KB Output is correct
4 Correct 18 ms 21580 KB Output is correct
5 Correct 19 ms 21524 KB Output is correct
6 Correct 23 ms 21616 KB Output is correct
7 Correct 19 ms 21596 KB Output is correct
8 Correct 19 ms 21832 KB Output is correct
9 Correct 19 ms 21452 KB Output is correct
10 Correct 19 ms 21696 KB Output is correct
11 Correct 19 ms 21708 KB Output is correct
12 Correct 19 ms 21632 KB Output is correct
13 Correct 19 ms 22060 KB Output is correct
14 Correct 19 ms 22456 KB Output is correct
15 Correct 20 ms 22536 KB Output is correct
16 Correct 20 ms 23204 KB Output is correct
17 Correct 22 ms 22560 KB Output is correct
18 Correct 28 ms 23476 KB Output is correct
19 Correct 25 ms 24280 KB Output is correct
20 Correct 26 ms 25096 KB Output is correct
21 Correct 22 ms 22212 KB Output is correct
22 Correct 23 ms 22944 KB Output is correct
23 Correct 23 ms 23336 KB Output is correct
24 Correct 25 ms 23688 KB Output is correct
25 Correct 290 ms 56808 KB Output is correct
26 Correct 329 ms 84500 KB Output is correct
27 Correct 350 ms 92876 KB Output is correct
28 Correct 408 ms 141900 KB Output is correct
29 Correct 411 ms 134840 KB Output is correct
30 Correct 583 ms 264160 KB Output is correct
31 Correct 744 ms 357924 KB Output is correct
32 Correct 937 ms 508536 KB Output is correct
33 Correct 323 ms 84940 KB Output is correct
34 Correct 407 ms 147996 KB Output is correct
35 Correct 483 ms 189000 KB Output is correct
36 Correct 559 ms 274760 KB Output is correct
37 Correct 325 ms 57772 KB Output is correct
38 Correct 355 ms 85696 KB Output is correct
39 Correct 370 ms 94100 KB Output is correct
40 Correct 394 ms 142604 KB Output is correct
41 Correct 410 ms 143756 KB Output is correct
42 Correct 581 ms 269084 KB Output is correct
43 Correct 755 ms 351508 KB Output is correct
44 Correct 960 ms 510964 KB Output is correct
45 Correct 337 ms 86048 KB Output is correct
46 Correct 414 ms 148348 KB Output is correct
47 Correct 494 ms 188704 KB Output is correct
48 Correct 573 ms 275340 KB Output is correct