oj.uz

Submission #930139

# Submission time Handle Problem Language Result Execution time Memory
930139 2024-02-18T16:22:30 Z duckindog Klasika (COCI20_klasika) C++17
110 / 110
 510 ms 296860 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 + 10;
int n;
struct Query {
  int a, t;
  Query(int a = 0, int t = 0) : a(a), t(t) {}
};
vector<Query> Q[N];

struct trie {
  int maxBit = 30;
  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) {
      while (nwt.size() <= g) nwt.push_back(array<int, 2>());
      while (t.size() <= it) t.push_back(N);
      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& duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    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& duck : ad[u]) {
    int v, w; tie(v, w) = duck;
    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& duck : Q[u]) {
    int a = duck.a, time = duck.t;
    answer[time] = node[u].get(d[a], time);
  }

  ed[u] = it;
}

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

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

  cin >> n;
  int cnt = 1;
  for (int i = 1; i <= n; ++i) {
    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(Query(x, i));
    }
  }

  memset(answer, -1, sizeof answer);
  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:26:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   26 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:28: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]
   28 |       while (nwt.size() <= g) nwt.push_back(array<int, 2>());
      |              ~~~~~~~~~~~^~~~
klasika.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |       while (t.size() <= it) t.push_back(N);
      |              ~~~~~~~~~^~~~~
klasika.cpp: In member function 'int trie::get(int, int)':
klasika.cpp:41: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]
   41 |       while (nwt.size() <= g) nwt.push_back(array<int, 2>());
      |              ~~~~~~~~~~~^~~~
klasika.cpp:42:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |       while (t.size() <= it) t.push_back(N);
      |              ~~~~~~~~~^~~~~
klasika.cpp:43:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   43 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:46:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |         ret |= (1 << j - 1);
      |                      ~~^~~
klasika.cpp: In function 'int32_t main()':
klasika.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 7 ms 24196 KB Output is correct
4 Correct 7 ms 24156 KB Output is correct
5 Correct 7 ms 23900 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 7 ms 24152 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 7 ms 23900 KB Output is correct
10 Correct 7 ms 24156 KB Output is correct
11 Correct 7 ms 24156 KB Output is correct
12 Correct 7 ms 24156 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 7 ms 24196 KB Output is correct
4 Correct 7 ms 24156 KB Output is correct
5 Correct 7 ms 23900 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 7 ms 24152 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 7 ms 23900 KB Output is correct
10 Correct 7 ms 24156 KB Output is correct
11 Correct 7 ms 24156 KB Output is correct
12 Correct 7 ms 24156 KB Output is correct
13 Correct 9 ms 24412 KB Output is correct
14 Correct 9 ms 24684 KB Output is correct
15 Correct 8 ms 24924 KB Output is correct
16 Correct 8 ms 25224 KB Output is correct
17 Correct 9 ms 24744 KB Output is correct
18 Correct 8 ms 25180 KB Output is correct
19 Correct 9 ms 25692 KB Output is correct
20 Correct 9 ms 26072 KB Output is correct
21 Correct 8 ms 24412 KB Output is correct
22 Correct 9 ms 24956 KB Output is correct
23 Correct 9 ms 25440 KB Output is correct
24 Correct 10 ms 25444 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 53896 KB Output is correct
2 Correct 136 ms 69352 KB Output is correct
3 Correct 152 ms 82376 KB Output is correct
4 Correct 220 ms 113628 KB Output is correct
5 Correct 175 ms 88720 KB Output is correct
6 Correct 291 ms 162164 KB Output is correct
7 Correct 371 ms 217780 KB Output is correct
8 Correct 510 ms 296860 KB Output is correct
9 Correct 154 ms 61108 KB Output is correct
10 Correct 186 ms 94988 KB Output is correct
11 Correct 253 ms 121748 KB Output is correct
12 Correct 279 ms 163228 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 7 ms 24196 KB Output is correct
4 Correct 7 ms 24156 KB Output is correct
5 Correct 7 ms 23900 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 7 ms 24152 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 7 ms 23900 KB Output is correct
10 Correct 7 ms 24156 KB Output is correct
11 Correct 7 ms 24156 KB Output is correct
12 Correct 7 ms 24156 KB Output is correct
13 Correct 9 ms 24412 KB Output is correct
14 Correct 9 ms 24684 KB Output is correct
15 Correct 8 ms 24924 KB Output is correct
16 Correct 8 ms 25224 KB Output is correct
17 Correct 9 ms 24744 KB Output is correct
18 Correct 8 ms 25180 KB Output is correct
19 Correct 9 ms 25692 KB Output is correct
20 Correct 9 ms 26072 KB Output is correct
21 Correct 8 ms 24412 KB Output is correct
22 Correct 9 ms 24956 KB Output is correct
23 Correct 9 ms 25440 KB Output is correct
24 Correct 10 ms 25444 KB Output is correct
25 Correct 110 ms 53896 KB Output is correct
26 Correct 136 ms 69352 KB Output is correct
27 Correct 152 ms 82376 KB Output is correct
28 Correct 220 ms 113628 KB Output is correct
29 Correct 175 ms 88720 KB Output is correct
30 Correct 291 ms 162164 KB Output is correct
31 Correct 371 ms 217780 KB Output is correct
32 Correct 510 ms 296860 KB Output is correct
33 Correct 154 ms 61108 KB Output is correct
34 Correct 186 ms 94988 KB Output is correct
35 Correct 253 ms 121748 KB Output is correct
36 Correct 279 ms 163228 KB Output is correct
37 Correct 145 ms 49988 KB Output is correct
38 Correct 161 ms 71480 KB Output is correct
39 Correct 186 ms 82696 KB Output is correct
40 Correct 197 ms 114092 KB Output is correct
41 Correct 196 ms 92260 KB Output is correct
42 Correct 301 ms 163584 KB Output is correct
43 Correct 391 ms 213404 KB Output is correct
44 Correct 502 ms 296096 KB Output is correct
45 Correct 153 ms 62364 KB Output is correct
46 Correct 227 ms 96308 KB Output is correct
47 Correct 252 ms 122548 KB Output is correct
48 Correct 287 ms 164676 KB Output is correct