oj.uz

Submission #197959

# Submission time Handle Problem Language Result Execution time Memory
197959 2020-01-24T12:09:50 Z model_code Klasika (COCI20_klasika) C++17
33 / 110
 364 ms 70736 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 Node {
  Node *zero, *one;
  Node () {
    zero = one = NULL;
  }
} root;

int q, n, t;
int rxor[MAXN];

void trie_add(Node *node, int bit, int val) {
  if (bit < 0) return;
  if (val & (1 << bit)) {
    if (node->one == NULL) node->one = new Node();
    trie_add(node->one, bit - 1, val);
  } else {
    if (node->zero == NULL) node->zero = new Node();
    trie_add(node->zero, bit - 1, val);
  }
}

int trie_get(Node *node, int bit, int val) {
  if (bit < 0) return 0;
  if ((val & (1 << bit)) == 0) { // want 1
    if (node->one == NULL)
      return trie_get(node->zero, bit - 1, val);
    else
      return (1 << bit) + trie_get(node->one, bit - 1, val);
  } else { // want 0
    if (node->zero == NULL)
      return trie_get(node->one, bit - 1, val);
    else
      return (1 << bit) + trie_get(node->zero, bit - 1, val);
  }
}

int main(void) {
  int n = 1;
  scanf("%d", &q);

  trie_add(&root, 30, 0);
  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;
      rxor[n] = y ^ rxor[x];
      trie_add(&root, 30, rxor[n]);
      ++n;
    } else {
      int a, b;
      scanf("%d%d", &a, &b); --a; --b;
      printf("%d\n", trie_get(&root, 30, rxor[a]));
    }
  }

  return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
klasika.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
klasika.cpp:60:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &x, &y); --x;
       ~~~~~^~~~~~~~~~~~~~~~
klasika.cpp:66:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &a, &b); --a; --b;
       ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 21960 KB Output is correct
2 Correct 328 ms 39120 KB Output is correct
3 Correct 339 ms 54936 KB Output is correct
4 Correct 353 ms 70596 KB Output is correct
5 Correct 277 ms 22012 KB Output is correct
6 Correct 315 ms 39156 KB Output is correct
7 Correct 339 ms 55140 KB Output is correct
8 Correct 364 ms 70644 KB Output is correct
9 Correct 276 ms 21888 KB Output is correct
10 Correct 313 ms 39168 KB Output is correct
11 Correct 340 ms 55272 KB Output is correct
12 Correct 352 ms 70736 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -