Submission #638298

#	Time	Username	Problem	Language	Result	Execution time	Memory
638298		iee	Nivelle (COCI20_nivelle)	C++17	0 / 110	265 ms	395720 KiB

nivelle

// iee
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <map>

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0; int f = 1, ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 3e5 + 5, M = 4e6 + 5;
int n, dfn_l[N], dfn_r[N], trie[M][3], tot = 1, idx, val[N];
int q;
int qry[N][3];
set<int> s[M];
vector<pair<int, int>> e[N];
void dfs(int u, int pr) {
  dfn_l[u] = ++idx;
  for (auto ver: e[u]) {
    int v, w;
    tie(v, w) = ver;
    if (v == pr) continue;
    val[v] = (val[u] ^ w);
    dfs(v, u);
  }
  dfn_r[u] = idx;
}
void insert(int x, int dfn) {
  int cur = 1;
  s[cur].emplace(dfn);
  per(i, 30, 0) {
    int &to = trie[cur][x >> i & 1];
    if (!to) to = ++tot;
    cur = to;
    s[cur].emplace(dfn);
  }
}
int query(int x, int l, int r) {
  int cur = 1, ans = 0;
  per(i, 30, 0) {
    int to = trie[cur][x >> i & 1 ^ 1];
    bool ok = !!to;
    auto it = s[to].lower_bound(l);
    ok &= it != s[to].end() && (*it) <= r;
    if (ok) cur = to, ans += (1 << i);
    else cur = trie[cur][x >> i & 1];
  }
  return ans;
}
void work(int CASE) {
  scanf("%d", &q);
  ++n;
  rep(i, 1, q) {
    char op[10];
    scanf("%s%d%d", op, &qry[i][1], &qry[i][2]);
    if (op[0] == 'A') {
      qry[i][0] = 1;
      ++n;
      e[qry[i][1]].emplace_back(n, qry[i][2]);
      e[n].emplace_back(qry[i][1], qry[i][2]);
      qry[i][1] = n;
    } else {
      qry[i][0] = 0;
    }
  }
  dfs(1, 0);
  insert(0, 1);
  rep(i, 1, q) {
    if (qry[i][0]) {
      insert(val[qry[i][1]], dfn_l[qry[i][1]]);
    } else {
      printf("%d\n", query(val[qry[i][1]], dfn_l[qry[i][2]], dfn_r[qry[i][2]]));
    }
  }
}

Compilation message (stderr)

nivelle.cpp: In function 'int query(int, int, int)':
nivelle.cpp:62:31: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   62 |     int to = trie[cur][x >> i & 1 ^ 1];
      |                        ~~~~~~~^~~
nivelle.cpp: In function 'void work(int)':
nivelle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
nivelle.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%s%d%d", op, &qry[i][1], &qry[i][2]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 17
• Subtask 3: 0 / 13
• Subtask 4: 0 / 25
• Subtask 5: 0 / 48