oj.uz

Submission #930212

# Submission time Handle Problem Language Result Execution time Memory
930212 2024-02-19T03:06:51 Z duckindog Klasika (COCI20_klasika) C++17
110 / 110
 521 ms 298684 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
const int N = 2e5 + 1;
int n;
vector<pair<int, int>> Q[N];

int maxBit = 30;
struct trie {
  int it;
  vector<array<int, 2>> nwt;
  vector<int> t;

  void add(int val, int time) {
    int g = 0;
    for (int j = maxBit; j >= 1; --j) {
      int bit = (val >> j - 1 & 1);

      while (nwt.size() <= g) nwt.push_back(array<int, 2>());

      if (!nwt[g][bit]) nwt[g][bit] = ++it;
      g = nwt[g][bit];

      while (t.size() <= it) t.push_back(N);
      t[g] = min(t[g], time);
    }
  }
  int get(int val, int time) {
    int g = 0;
    int ret = 0;
    for (int j = maxBit; j >= 1; --j) {
      int bit = (val >> j - 1 & 1);

      if (nwt[g][!bit] && t[nwt[g][!bit]] <= time) {
        ret |= (1 << j - 1);
        g = nwt[g][!bit];
      } else g = nwt[g][bit];

    }
    return ret;
  }

  void clear() {
    nwt.clear();
    t.clear();
  }

} node[N];

vector<pii> ad[N];
int d[N], t[N];
int answer[N];

int it;
int st[N], ed[N], mask[N];

void dfs(int u, int pre = 0) {
  mask[st[u] = ++it] = u;
  int best = 0;
  for (const auto& [v, w] : ad[u]) {
    if (v == pre) continue;
    dfs(v, u);
    if (!best || node[v].nwt.size() > node[best].nwt.size()) best = v;
  }

  swap(node[u], node[best]);
  for (const auto& [v, w] : ad[u]) {
    if (v == pre || v == best) continue;

    for (int i = st[v]; i <= ed[v]; ++i) node[u].add(d[mask[i]], t[mask[i]]);
    node[v].clear();
  }
  node[u].add(d[u], t[u]);
  for (const auto& [a, time] : Q[u]) {
    answer[time] = node[u].get(d[a], time);
  }

  ed[u] = it;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  cin >> n;
  int cnt = 1;
  for (int i = 1; i <= n; ++i) {
    answer[i] = -1;
    string ty;
    int x, y;
    cin >> ty >> x >> y;
    if (ty == "Add") {
      cnt += 1;
      ad[x].push_back({cnt, y});
      ad[cnt].push_back({x, y});
      d[cnt] = (d[x] ^ y);
      t[cnt] = i;
    } else {
      Q[y].push_back({x, i});
    }
  }

  dfs(1);
  for (int i = 1; i <= n; ++i)
    if (answer[i] != -1) cout << answer[i] << "\n";
}

Compilation message

klasika.cpp: In member function 'void trie::add(int, int)':
klasika.cpp:22:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   22 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:24:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |       while (nwt.size() <= g) nwt.push_back(array<int, 2>());
      |              ~~~~~~~~~~~^~~~
klasika.cpp:29:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |       while (t.size() <= it) t.push_back(N);
      |              ~~~~~~~~~^~~~~
klasika.cpp: In member function 'int trie::get(int, int)':
klasika.cpp:37:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   37 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:40:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |         ret |= (1 << j - 1);
      |                      ~~^~~
klasika.cpp: In function 'int32_t main()':
klasika.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Output is correct
2 Correct 7 ms 25176 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 8 ms 25432 KB Output is correct
5 Correct 8 ms 25176 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25288 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 9 ms 25176 KB Output is correct
10 Correct 8 ms 25332 KB Output is correct
11 Correct 8 ms 25432 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Output is correct
2 Correct 7 ms 25176 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 8 ms 25432 KB Output is correct
5 Correct 8 ms 25176 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25288 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 9 ms 25176 KB Output is correct
10 Correct 8 ms 25332 KB Output is correct
11 Correct 8 ms 25432 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct
13 Correct 10 ms 25692 KB Output is correct
14 Correct 11 ms 25948 KB Output is correct
15 Correct 10 ms 26116 KB Output is correct
16 Correct 10 ms 26500 KB Output is correct
17 Correct 9 ms 25860 KB Output is correct
18 Correct 9 ms 26460 KB Output is correct
19 Correct 11 ms 26936 KB Output is correct
20 Correct 10 ms 27352 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 9 ms 26204 KB Output is correct
23 Correct 10 ms 26460 KB Output is correct
24 Correct 10 ms 26652 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 50376 KB Output is correct
2 Correct 135 ms 71368 KB Output is correct
3 Correct 162 ms 81012 KB Output is correct
4 Correct 187 ms 112764 KB Output is correct
5 Correct 174 ms 94124 KB Output is correct
6 Correct 286 ms 162220 KB Output is correct
7 Correct 386 ms 219416 KB Output is correct
8 Correct 514 ms 298388 KB Output is correct
9 Correct 148 ms 64684 KB Output is correct
10 Correct 179 ms 98020 KB Output is correct
11 Correct 233 ms 125328 KB Output is correct
12 Correct 279 ms 165516 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Output is correct
2 Correct 7 ms 25176 KB Output is correct
3 Correct 9 ms 25432 KB Output is correct
4 Correct 8 ms 25432 KB Output is correct
5 Correct 8 ms 25176 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25288 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 9 ms 25176 KB Output is correct
10 Correct 8 ms 25332 KB Output is correct
11 Correct 8 ms 25432 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct
13 Correct 10 ms 25692 KB Output is correct
14 Correct 11 ms 25948 KB Output is correct
15 Correct 10 ms 26116 KB Output is correct
16 Correct 10 ms 26500 KB Output is correct
17 Correct 9 ms 25860 KB Output is correct
18 Correct 9 ms 26460 KB Output is correct
19 Correct 11 ms 26936 KB Output is correct
20 Correct 10 ms 27352 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 9 ms 26204 KB Output is correct
23 Correct 10 ms 26460 KB Output is correct
24 Correct 10 ms 26652 KB Output is correct
25 Correct 118 ms 50376 KB Output is correct
26 Correct 135 ms 71368 KB Output is correct
27 Correct 162 ms 81012 KB Output is correct
28 Correct 187 ms 112764 KB Output is correct
29 Correct 174 ms 94124 KB Output is correct
30 Correct 286 ms 162220 KB Output is correct
31 Correct 386 ms 219416 KB Output is correct
32 Correct 514 ms 298388 KB Output is correct
33 Correct 148 ms 64684 KB Output is correct
34 Correct 179 ms 98020 KB Output is correct
35 Correct 233 ms 125328 KB Output is correct
36 Correct 279 ms 165516 KB Output is correct
37 Correct 141 ms 54244 KB Output is correct
38 Correct 164 ms 71984 KB Output is correct
39 Correct 187 ms 84424 KB Output is correct
40 Correct 201 ms 111624 KB Output is correct
41 Correct 213 ms 95776 KB Output is correct
42 Correct 298 ms 173204 KB Output is correct
43 Correct 442 ms 216752 KB Output is correct
44 Correct 521 ms 298684 KB Output is correct
45 Correct 149 ms 67020 KB Output is correct
46 Correct 208 ms 98576 KB Output is correct
47 Correct 252 ms 124464 KB Output is correct
48 Correct 310 ms 165684 KB Output is correct