Submission #802478

#	Time	Username	Problem	Language	Result	Execution time	Memory
802478		mgl_diamond	Klasika (COCI20_klasika)	C++17	110 / 110	2617 ms	486956 KiB

klasika

#include <bits/stdc++.h>

#define conqueror_of_uraqt int main()
#define xuong cout << "\n"
#define debug(x) cout << #x << ": " << x << "\n"
#define go(i,l,r) for(int i=(l); i<=(r); ++i)
#define rev(i,l,r) for(int i=(r); i>=(l); --i)
#define x first
#define y second
#define vec vector
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define uni(a) a.erase(unique(all(a)), a.end())
#define C make_pair
#define file "input"

template<class T> bool ckmax(T &a, const T b) { if (a<b) return a=b,1; return 0; }
template<class T> bool ckmin(T &a, const T b) { if (a>b) return a=b,1; return 0; }

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

struct node {
  int to[2];
  set<int> tmp;
  node() { memset(to, -1, sizeof(to)); }
};

vec<node> trie;
void built() { trie.push_back(node()); }
void add(int n, int idx) {
  trie[0].tmp.insert(idx);
  for(int i=30, cur=0; i>=0; --i) {
    int d = n>>i&1;
    if (trie[cur].to[d] == -1) {
      trie[cur].to[d] = sz(trie);
      trie.push_back(node());
    }
    cur = trie[cur].to[d];
    trie[cur].tmp.insert(idx);
  }
}
int query(int n, int l, int r) {
  auto it = trie[0].tmp.lower_bound(l);
  if (it == trie[0].tmp.end() || *it > r) exit(1);
  int ans = 0;
  for(int i=30, cur=0; i>=0; --i) {
    assert(cur >= 0);
    int d = n>>i&1;
    if (trie[cur].to[d^1] == -1) cur = trie[cur].to[d];
    else {
      auto it = trie[trie[cur].to[d^1]].tmp.lower_bound(l);
      if (it == trie[trie[cur].to[d^1]].tmp.end() || *it > r) cur = trie[cur].to[d];
      else {
        cur = trie[cur].to[d^1];
        ans += (1 << i);
      }
    }
  }
  return ans;
}

const int mxN = 5e5+5;
int n, a[mxN], d[mxN], st[mxN], en[mxN];
vec<int> e[mxN];

int cnt = 0;
void dfs(int u) {
  st[u] = ++cnt;
  for(int v: e[u]) {
    dfs(v);
  }
  en[u] = cnt;
}

void solve() {
  built();
  add(0, 1);
  vec<pair<bool, pair<pii, int>>> querys;
  int q, exist = 1; cin >> q;
  for(int i=1; i<=q; ++i) {
    string s; int u, v;
    cin >> s >> u >> v;
    if (s == "Add") {
      ++exist;
      e[u].push_back(exist);
      querys.push_back(C(0, C(C(u, exist), v)));
    } else {
      querys.push_back(C(1, C(C(u, v), 0)));
    }
  }
  dfs(1);
  for(int i=0; i<q; ++i) {
    auto proc = querys[i];
    if (proc.x == 0) {
      int u = proc.y.x.x, v = proc.y.x.y, w = proc.y.y;
      d[v] = d[u] ^ w;
      add(d[v], st[v]);
    } else {
      int u = proc.y.x.x, v = proc.y.x.y;
      cout << query(d[u], st[v], en[v]) << "\n";
    }
  }
}

conqueror_of_uraqt {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

Compilation message (stderr)

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

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