oj.uz

Submission #846086

# Submission time Handle Problem Language Result Execution time Memory
846086 2023-09-07T09:34:35 Z Koful123 Klasika (COCI20_klasika) C++17
110 / 110
 2273 ms 438376 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define TRACE(x) cerr << #x << " " << x << endl
    #define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
    #define REP(i, n) FOR(i, 0, n)
    #define _ << " " <<
     
    typedef long long llint;
     
    const int MAXN = 2e5 + 10;
     
    struct Query {
      bool print;
      int x, y;
      Query() {}
      Query(bool print, int x, int y) : print(print), x(x), y(y) {}
    };
     
    struct Node {
      set<int> ids;
      Node *zero, *one;
      Node () {
        zero = one = NULL;
      }
    } root;
     
    int q, n, t;
    int l[MAXN], r[MAXN], rxor[MAXN];
     
    vector<pair<int, int>> v[MAXN];
    vector<Query> Q;
     
    void dfs(int node, int dad, int xval) {
      l[node] = ++t;
      rxor[node] = xval;
      for (const auto &p : v[node]) {
        int nxt = p.first;
        int w = p.second;
        if (nxt == dad) continue;
        dfs(nxt, node, xval ^ w);
      }
      r[node] = t;
    }
     
    void trie_add(Node *node, int bit, int val, int id) {
      node->ids.insert(id);
      if (bit < 0) return;
      if (val & (1 << bit)) {
        if (node->one == NULL) node->one = new Node();
        trie_add(node->one, bit - 1, val, id);
      } else {
        if (node->zero == NULL) node->zero = new Node();
        trie_add(node->zero, bit - 1, val, id);
      }
    }
     
    int trie_get(Node *node, int bit, int val, int from, int to) {
      if (bit < 0) return 0;
      if ((val & (1 << bit)) == 0) { // want 1
        if (node->one == NULL ||
            node->one->ids.lower_bound(from) == node->one->ids.upper_bound(to))
          return trie_get(node->zero, bit - 1, val, from, to);
        else
          return (1 << bit) + trie_get(node->one, bit - 1, val, from, to);
      } else { // want 0
        if (node->zero == NULL ||
            node->zero->ids.lower_bound(from) == node->zero->ids.upper_bound(to))
          return trie_get(node->one, bit - 1, val, from, to);
        else
          return (1 << bit) + trie_get(node->zero, bit - 1, val, from, to);
      }
    }
     
    int main(void) {
      int n = 1;
      scanf("%d", &q);
      for (int i = 0; i < q; ++i) {
        char s[10];
        scanf("%s", s);
        if (s[0] == 'A') {
          int x, y;
          scanf("%d%d", &x, &y); --x;
          Q.emplace_back(false, n, y);
          v[x].emplace_back(n, y);
          v[n].emplace_back(x, y);
          ++n;
        } else {
          int a, b;
          scanf("%d%d", &a, &b); --a; --b;
          Q.emplace_back(true, a, b);
        }
      }
     
      dfs(0, -1, 0);
     
      trie_add(&root, 30, 0, l[0]);
      int i = 1;
      for (const auto &qq : Q) {
        if (!qq.print)
          trie_add(&root, 30, rxor[qq.x], l[qq.x]);
        else
          printf("%d\n", trie_get(&root, 30, rxor[qq.x], l[qq.y], r[qq.y]));
        ++i;
      }
     
      return 0;
    }

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:78:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |       scanf("%d", &q);
      |       ~~~~~^~~~~~~~~~
klasika.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%s", s);
      |         ~~~~~^~~~~~~~~
klasika.cpp:84:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |           scanf("%d%d", &x, &y); --x;
      |           ~~~~~^~~~~~~~~~~~~~~~
klasika.cpp:91:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |           scanf("%d%d", &a, &b); --a; --b;
      |           ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7316 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7316 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 5 ms 9308 KB Output is correct
15 Correct 7 ms 10584 KB Output is correct
16 Correct 8 ms 11868 KB Output is correct
17 Correct 4 ms 8028 KB Output is correct
18 Correct 5 ms 9304 KB Output is correct
19 Correct 7 ms 10588 KB Output is correct
20 Correct 8 ms 11612 KB Output is correct
21 Correct 4 ms 8076 KB Output is correct
22 Correct 6 ms 9560 KB Output is correct
23 Correct 7 ms 10588 KB Output is correct
24 Correct 8 ms 11608 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 123952 KB Output is correct
2 Correct 1099 ms 231024 KB Output is correct
3 Correct 1502 ms 334272 KB Output is correct
4 Correct 1779 ms 437776 KB Output is correct
5 Correct 648 ms 121796 KB Output is correct
6 Correct 1139 ms 227220 KB Output is correct
7 Correct 1630 ms 328352 KB Output is correct
8 Correct 2070 ms 429724 KB Output is correct
9 Correct 608 ms 121484 KB Output is correct
10 Correct 1056 ms 228332 KB Output is correct
11 Correct 1441 ms 331656 KB Output is correct
12 Correct 1816 ms 431916 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7316 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 5 ms 9308 KB Output is correct
15 Correct 7 ms 10584 KB Output is correct
16 Correct 8 ms 11868 KB Output is correct
17 Correct 4 ms 8028 KB Output is correct
18 Correct 5 ms 9304 KB Output is correct
19 Correct 7 ms 10588 KB Output is correct
20 Correct 8 ms 11612 KB Output is correct
21 Correct 4 ms 8076 KB Output is correct
22 Correct 6 ms 9560 KB Output is correct
23 Correct 7 ms 10588 KB Output is correct
24 Correct 8 ms 11608 KB Output is correct
25 Correct 712 ms 123952 KB Output is correct
26 Correct 1099 ms 231024 KB Output is correct
27 Correct 1502 ms 334272 KB Output is correct
28 Correct 1779 ms 437776 KB Output is correct
29 Correct 648 ms 121796 KB Output is correct
30 Correct 1139 ms 227220 KB Output is correct
31 Correct 1630 ms 328352 KB Output is correct
32 Correct 2070 ms 429724 KB Output is correct
33 Correct 608 ms 121484 KB Output is correct
34 Correct 1056 ms 228332 KB Output is correct
35 Correct 1441 ms 331656 KB Output is correct
36 Correct 1816 ms 431916 KB Output is correct
37 Correct 1219 ms 124128 KB Output is correct
38 Correct 1697 ms 230864 KB Output is correct
39 Correct 1929 ms 336660 KB Output is correct
40 Correct 2060 ms 438376 KB Output is correct
41 Correct 1134 ms 121996 KB Output is correct
42 Correct 1650 ms 226908 KB Output is correct
43 Correct 2025 ms 328220 KB Output is correct
44 Correct 2273 ms 428860 KB Output is correct
45 Correct 1216 ms 121140 KB Output is correct
46 Correct 1795 ms 227956 KB Output is correct
47 Correct 2043 ms 329296 KB Output is correct
48 Correct 2136 ms 431356 KB Output is correct