oj.uz

Submission #492768

# Submission time Handle Problem Language Result Execution time Memory
492768 2021-12-08T20:50:36 Z pauloamed Klasika (COCI20_klasika) C++14
0 / 110
 227 ms 87532 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){
    propagate_xor(curr_node, curr_bit);
    // if(curr_bit == 31){
    //   added.push_back(num);
    // }
    nodes[curr_node].size++;
    if(curr_bit == -1) return;

    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){
    propagate_xor(curr_node, curr_bit);
    // want to max (num ^ x)
    if(curr_bit == -1) return 0; // base recursion case

    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];

namespace LCA{
  int st[MAXN][MAXLOG];
  int lvl[MAXN];

  void init_dfs(int x, int par){
    st[x][0] = par;
    if(par != -1) lvl[x] = lvl[par] + 1;
    for(auto y : v[x]) if(y != par) init_dfs(y, x);
  }

  void init_st(){
    for(int x = 1; x < MAXLOG; ++x){
      for(int i = 0; i < MAXN; ++i){
        if(st[i][x-1] == -1) st[i][x] = -1;
        else st[i][x] = st[st[i][x-1]][x-1];
      }
    }
  }

  void init(int root){
    init_dfs(root, -1); init_st();
  }

  int lca(int x, int y){
    if(lvl[x] < lvl[y]) swap(x, y); // x is deeper

    int falta_subir = (lvl[x] - lvl[y]);

    for(int i = MAXLOG-1; i >= 0; --i){
      if((1<<i) <= falta_subir){
        falta_subir -= (1<<i);
        x = st[x][i];
      }
    }

    if(x == y) return x;

    for(int i = MAXLOG-1; i >= 0; --i){
      if(st[x][i] != st[y][i]){
        x = st[x][i];
        y = st[y][i];
      }
    }
    return st[x][0];
  }
}

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];

int 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];

int solve(int x, int p){
  int heavy_child = -1;
  int max_size = -1;

  for (auto k : v[x]){
    if (k != p){
      if (sz[k] > max_size){
        max_size = sz[k];
        heavy_child = k;
      }
    }
  }

  
  for (auto k : v[x]){
    if (k != p){
      solve(k, x);
    }
  }

  // cout << "hc: " << x << " " << heavy_child << endl; 
  if(heavy_child != -1){
    swap(tries[x], tries[heavy_child]);

    tries[x].xor_all(w[heavy_child]);

    for (auto k : v[x]){
      if (k != p && k != heavy_child){
        // cout << k << " " << beg[k] << " " << en[k] << endl;
        for(int it = beg[k]; it < en[k]; ++it){
          // cout << (xor_until[ver[it]] ^ xor_until[x]) << " " << time_added[ver[it]] << endl;
          tries[x].add(xor_until[ver[it]] ^ xor_until[x], time_added[ver[it]]);
        }
      }
    }
  }

  tries[x].add(0, time_added[x]); // 

  // cout << x << endl;
  // for(auto y : tries[x].added){
  //   cout << y << ", ";
  // }cout << endl;
  for(auto [t, a] : queries[x]){
    // cout << "query " << x << " " << t << " " << a << endl;
    ans[t] = a ^ tries[x].query_max(a, t);
  }

  tries[x].add(w[x], time_added[x]);
}

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}});
    }
  }

  LCA::init(1);
  preprocess_dfs(1, 0);

  for(auto [i, ab] : q){
    auto [start, subtree] = ab;

    int lca = LCA::lca(start, subtree);

    int val = xor_until[start] ^ xor_until[subtree];
    queries[subtree].push_back({i, val});
  }

  solve(1, 0);

  for(int i = 0; i < MAXN; ++i){
    if(ans[i] != -1) cout << ans[i] << "\n";
  }
}

Compilation message

klasika.cpp: In function 'int preprocess_dfs(int, int)':
klasika.cpp:162:1: warning: no return statement in function returning non-void [-Wreturn-type]
  162 | }
      | ^
klasika.cpp: In function 'int solve(int, int)':
klasika.cpp:210:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  210 |   for(auto [t, a] : queries[x]){
      |            ^
klasika.cpp:216:1: warning: no return statement in function returning non-void [-Wreturn-type]
  216 | }
      | ^
klasika.cpp: In function 'int main()':
klasika.cpp:244:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  244 |   for(auto [i, ab] : q){
      |            ^
klasika.cpp:245:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  245 |     auto [start, subtree] = ab;
      |          ^
klasika.cpp:247:9: warning: unused variable 'lca' [-Wunused-variable]
  247 |     int lca = LCA::lca(start, subtree);
      |         ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 75220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 75220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 87532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 75220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -