oj.uz

Submission #802478

# Submission time Handle Problem Language Result Execution time Memory
802478 2023-08-02T12:28:46 Z mgl_diamond Klasika (COCI20_klasika) C++17
110 / 110
 2617 ms 486956 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12456 KB Output is correct
4 Correct 6 ms 12500 KB Output is correct
5 Correct 6 ms 12204 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 6 ms 12372 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 6 ms 12204 KB Output is correct
10 Correct 6 ms 12480 KB Output is correct
11 Correct 6 ms 12500 KB Output is correct
12 Correct 6 ms 12456 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12456 KB Output is correct
4 Correct 6 ms 12500 KB Output is correct
5 Correct 6 ms 12204 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 6 ms 12372 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 6 ms 12204 KB Output is correct
10 Correct 6 ms 12480 KB Output is correct
11 Correct 6 ms 12500 KB Output is correct
12 Correct 6 ms 12456 KB Output is correct
13 Correct 9 ms 13600 KB Output is correct
14 Correct 10 ms 15148 KB Output is correct
15 Correct 11 ms 15412 KB Output is correct
16 Correct 13 ms 18216 KB Output is correct
17 Correct 9 ms 13552 KB Output is correct
18 Correct 12 ms 15148 KB Output is correct
19 Correct 15 ms 15432 KB Output is correct
20 Correct 14 ms 16320 KB Output is correct
21 Correct 9 ms 13508 KB Output is correct
22 Correct 10 ms 15148 KB Output is correct
23 Correct 12 ms 15340 KB Output is correct
24 Correct 12 ms 16296 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 128548 KB Output is correct
2 Correct 1055 ms 244768 KB Output is correct
3 Correct 1473 ms 300532 KB Output is correct
4 Correct 2087 ms 486688 KB Output is correct
5 Correct 655 ms 126872 KB Output is correct
6 Correct 1235 ms 241596 KB Output is correct
7 Correct 1808 ms 296360 KB Output is correct
8 Correct 2452 ms 480176 KB Output is correct
9 Correct 581 ms 127144 KB Output is correct
10 Correct 1089 ms 242172 KB Output is correct
11 Correct 1529 ms 298532 KB Output is correct
12 Correct 2057 ms 481372 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12456 KB Output is correct
4 Correct 6 ms 12500 KB Output is correct
5 Correct 6 ms 12204 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 6 ms 12372 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 6 ms 12204 KB Output is correct
10 Correct 6 ms 12480 KB Output is correct
11 Correct 6 ms 12500 KB Output is correct
12 Correct 6 ms 12456 KB Output is correct
13 Correct 9 ms 13600 KB Output is correct
14 Correct 10 ms 15148 KB Output is correct
15 Correct 11 ms 15412 KB Output is correct
16 Correct 13 ms 18216 KB Output is correct
17 Correct 9 ms 13552 KB Output is correct
18 Correct 12 ms 15148 KB Output is correct
19 Correct 15 ms 15432 KB Output is correct
20 Correct 14 ms 16320 KB Output is correct
21 Correct 9 ms 13508 KB Output is correct
22 Correct 10 ms 15148 KB Output is correct
23 Correct 12 ms 15340 KB Output is correct
24 Correct 12 ms 16296 KB Output is correct
25 Correct 634 ms 128548 KB Output is correct
26 Correct 1055 ms 244768 KB Output is correct
27 Correct 1473 ms 300532 KB Output is correct
28 Correct 2087 ms 486688 KB Output is correct
29 Correct 655 ms 126872 KB Output is correct
30 Correct 1235 ms 241596 KB Output is correct
31 Correct 1808 ms 296360 KB Output is correct
32 Correct 2452 ms 480176 KB Output is correct
33 Correct 581 ms 127144 KB Output is correct
34 Correct 1089 ms 242172 KB Output is correct
35 Correct 1529 ms 298532 KB Output is correct
36 Correct 2057 ms 481372 KB Output is correct
37 Correct 1069 ms 129112 KB Output is correct
38 Correct 1756 ms 245212 KB Output is correct
39 Correct 2017 ms 302916 KB Output is correct
40 Correct 2281 ms 486956 KB Output is correct
41 Correct 1217 ms 127256 KB Output is correct
42 Correct 1830 ms 241820 KB Output is correct
43 Correct 2278 ms 296584 KB Output is correct
44 Correct 2617 ms 480388 KB Output is correct
45 Correct 1258 ms 127628 KB Output is correct
46 Correct 1890 ms 242608 KB Output is correct
47 Correct 2108 ms 297308 KB Output is correct
48 Correct 2487 ms 481612 KB Output is correct