oj.uz

Submission #624688

# Submission time Handle Problem Language Result Execution time Memory
624688 2022-08-08T15:36:01 Z MilosMilutinovic Klasika (COCI20_klasika) C++14
33 / 110
 2361 ms 524288 KB 
/**
 *    author:  wxhtzdy
 *    created: 08.08.2022 17:17:05
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int q;
  cin >> q;
  vector<string> op(q);
  vector<int> x(q);
  vector<int> y(q);
  int n = 1;
  vector<vector<pair<int, int>>> g(1);
  for (int i = 0; i < q; i++) {
    cin >> op[i] >> x[i] >> y[i];
    if (op[i] == "Add") {
      --x[i];
      g.push_back({});
      g[x[i]].emplace_back(n, y[i]);  
      n += 1;
    } else {
      --x[i]; --y[i];
    }
  }
  vector<int> dep(n);
  vector<int> tin(n);
  vector<int> tout(n);
  int T = -1;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = ++T;
    for (auto& p : g[v]) {
      int u = p.first;
      int w = p.second;
      if (u != pr) {
        dep[u] = dep[v] ^ w;
        Dfs(u, v);
      }
    }
    tout[v] = T;
  };
  Dfs(0, 0);
  int idx = 1;
  vector<set<int>> ids(1);
  vector<vector<int>> trie(1, vector<int>(2, -1));
  auto Add = [&](int v, int id) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
      int bit = (v >> i & 1);
      if (trie[p][bit] == -1) {
        trie[p][bit] = (int) trie.size();
        trie.push_back(vector<int>(2, -1));
        ids.push_back({});
      }    
      p = trie[p][bit];
      ids[p].insert(id);     
    }
  };
  Add(dep[0], tin[0]);
  for (int i = 0; i < q; i++) {
    if (op[i] == "Add") {
      Add(dep[idx], tin[idx]);
      idx += 1;  
    } else {
      int p = 0;
      int ans = 0;
      for (int j = 30; j >= 0; j--) {
        int bit = (dep[x[i]] >> j & 1);
        if (trie[p][bit ^ 1] != -1) {
          auto it = ids[trie[p][bit ^ 1]].lower_bound(tin[y[i]]);
          if (it != ids[trie[p][bit ^ 1]].end() && *it <= tout[y[i]]) {
            ans += (1 << j);
            p = trie[p][bit ^ 1];
          } else {
            p = trie[p][bit];
          }
        } else {
          p = trie[p][bit];
        }
      }
      cout << ans << '\n';
    }  
  }                         
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 576 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 964 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 576 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 964 KB Output is correct
13 Correct 5 ms 2228 KB Output is correct
14 Correct 7 ms 4140 KB Output is correct
15 Correct 9 ms 5056 KB Output is correct
16 Correct 14 ms 7868 KB Output is correct
17 Correct 4 ms 2124 KB Output is correct
18 Correct 7 ms 4024 KB Output is correct
19 Correct 8 ms 4800 KB Output is correct
20 Correct 10 ms 6080 KB Output is correct
21 Correct 5 ms 2252 KB Output is correct
22 Correct 7 ms 4036 KB Output is correct
23 Correct 9 ms 4800 KB Output is correct
24 Correct 11 ms 6080 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 144104 KB Output is correct
2 Correct 1611 ms 282800 KB Output is correct
3 Correct 2361 ms 378748 KB Output is correct
4 Runtime error 2244 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 576 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 964 KB Output is correct
13 Correct 5 ms 2228 KB Output is correct
14 Correct 7 ms 4140 KB Output is correct
15 Correct 9 ms 5056 KB Output is correct
16 Correct 14 ms 7868 KB Output is correct
17 Correct 4 ms 2124 KB Output is correct
18 Correct 7 ms 4024 KB Output is correct
19 Correct 8 ms 4800 KB Output is correct
20 Correct 10 ms 6080 KB Output is correct
21 Correct 5 ms 2252 KB Output is correct
22 Correct 7 ms 4036 KB Output is correct
23 Correct 9 ms 4800 KB Output is correct
24 Correct 11 ms 6080 KB Output is correct
25 Correct 887 ms 144104 KB Output is correct
26 Correct 1611 ms 282800 KB Output is correct
27 Correct 2361 ms 378748 KB Output is correct
28 Runtime error 2244 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -