Submission #1123515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123515		VinhLuu	Klasika (COCI20_klasika)	C++20	110 / 110	1598 ms	123596 KiB

klasika

#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int n, q, a[N], d[N], sub[N], f[22][N], in[N], en[N], demin, be[N], type[N], A[N], B[N], kq[N];
vector<pair<int,int>> adj[N];
vector<int> Q[N];

struct trie {
  trie* child[2];
  int tmp;
  trie() {
    child[0] = child[1] = NULL;
    tmp = q + 1;
  }
};

void del(trie* p) {
  if(p -> child[0] != NULL) del(p -> child[0]);
  if(p -> child[1] != NULL) del(p -> child[1]);
  delete(p);
}

trie* root;

void pre(int u,int v) {
  sub[u] = 1;
  in[u] = ++demin;
  be[demin] = u;
  if(u == 1) for(int i = 0; i <= 18; i ++) f[i][u] = u;
  else {
    f[0][u] = v;
    for(int i = 1; i <= 18; i ++)
      f[i][u] = f[i - 1][f[i - 1][u]];
  }
  for(auto [j, w] : adj[u]) if(j != v) {
    d[j] = (d[u] ^ w);
    pre(j, u);
    sub[u] += sub[j];
  }
  en[u] = demin;
}

bool kt(int u,int v) {
  return in[u] <= in[v] && in[v] <= en[u];
}

int LCA(int u,int v) {
  if(kt(u, v)) return u;
  int kq = u;
  for(int i = 18; i >= 0; i --) if(kt(f[i][u], v)) {
    kq = f[i][u];
  }else u = f[i][u];
  return kq;
}

int st[N], out[N], rev[N], stt;

void add(int x,int time) {
  trie* p = root;
  for(int i = 30; i >= 0; i --) {
    int bit = (x >> i) & 1;
    if(p -> child[bit] == NULL) p -> child[bit] = new trie();
    p = p -> child[bit];
    p -> tmp = min(p -> tmp, time);
  }
}

int get(int val,int time) {
  int ret = 0;
  trie* p = root;
  for(int i = 30; i >= 0; i --) {
    int bit = (val >> i) & 1;
    if(p -> child[(bit ^ 1)] != NULL && p -> child[(bit ^ 1)] -> tmp <= time) {
      ret = (ret + (1 << i));
      p = p -> child[(bit ^ 1)];
    }else p = p -> child[bit];
  }
  return ret;

}

void dfs(int u,int v) {
  st[u] = ++stt;
  rev[stt] = u;
  int mx = 0;
  for(auto [j, w] : adj[u]) if(j != v && sub[j] > sub[mx]) mx = j;
  for(auto [j, w] : adj[u]) if(j != v && j != mx) {
    dfs(j, u);
    del(root);
    root = new trie();
  }

  if(mx) dfs(mx, u);

  for(auto [j , w] : adj[u]) if(j != v && j != mx) {
    for(int i = st[j]; i <= out[j]; i ++) {
      int x = rev[i];
      add(d[x], a[x]);
    }
  }

  add(d[u], a[u]);

  for(auto j : Q[u]) {
    int val = d[A[j]];
    kq[j] = get(val, j);
  }

  out[u] = stt;
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> q;
  n = 1;
  for(int i = 1; i <= q; i ++) {
    string s; cin >> s >> A[i] >> B[i];
    if(s[0] == 'A') type[i] = 1;
    else type[i] = 2;
    if(type[i] == 1) {
      n++;
      a[n] = i;
      adj[A[i]].push_back({n, B[i]});
    }
  }

  root = new trie();

  pre(1, 0);

  for(int i = 1; i <= q; i ++) if(type[i] == 2) {
    Q[B[i]].push_back(i);
  }

  dfs(1, 0);

  for(int i = 1; i <= q; i ++) if(type[i] == 2) cout << kq[i] << "\n";
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44