oj.uz

Submission #932121

# Submission time Handle Problem Language Result Execution time Memory
932121 2024-02-23T03:23:43 Z duckindog Klasika (COCI20_klasika) C++17
110 / 110
 555 ms 304424 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<pii> Q[N];

unsigned char 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:38:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   38 |       int bit = (val >> j - 1 & 1);
      |                         ~~^~~
klasika.cpp:41:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |         ret |= (1 << j - 1);
      |                      ~~^~~
klasika.cpp: In function 'int32_t main()':
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.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB Output is correct
2 Correct 8 ms 25292 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25436 KB Output is correct
5 Correct 8 ms 25272 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 6 ms 25332 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 6 ms 25176 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 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 6 ms 25180 KB Output is correct
2 Correct 8 ms 25292 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25436 KB Output is correct
5 Correct 8 ms 25272 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 6 ms 25332 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 6 ms 25176 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct
13 Correct 7 ms 25692 KB Output is correct
14 Correct 8 ms 25912 KB Output is correct
15 Correct 9 ms 26120 KB Output is correct
16 Correct 9 ms 26348 KB Output is correct
17 Correct 8 ms 25948 KB Output is correct
18 Correct 8 ms 26456 KB Output is correct
19 Correct 9 ms 26968 KB Output is correct
20 Correct 9 ms 27352 KB Output is correct
21 Correct 8 ms 25852 KB Output is correct
22 Correct 8 ms 26200 KB Output is correct
23 Correct 9 ms 26456 KB Output is correct
24 Correct 9 ms 26652 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 56100 KB Output is correct
2 Correct 143 ms 72836 KB Output is correct
3 Correct 145 ms 81416 KB Output is correct
4 Correct 164 ms 114248 KB Output is correct
5 Correct 164 ms 94248 KB Output is correct
6 Correct 257 ms 163508 KB Output is correct
7 Correct 360 ms 220768 KB Output is correct
8 Correct 507 ms 302100 KB Output is correct
9 Correct 136 ms 64000 KB Output is correct
10 Correct 182 ms 98784 KB Output is correct
11 Correct 213 ms 124280 KB Output is correct
12 Correct 254 ms 166544 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25180 KB Output is correct
2 Correct 8 ms 25292 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25436 KB Output is correct
5 Correct 8 ms 25272 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 6 ms 25332 KB Output is correct
8 Correct 8 ms 25436 KB Output is correct
9 Correct 6 ms 25176 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25436 KB Output is correct
12 Correct 8 ms 25436 KB Output is correct
13 Correct 7 ms 25692 KB Output is correct
14 Correct 8 ms 25912 KB Output is correct
15 Correct 9 ms 26120 KB Output is correct
16 Correct 9 ms 26348 KB Output is correct
17 Correct 8 ms 25948 KB Output is correct
18 Correct 8 ms 26456 KB Output is correct
19 Correct 9 ms 26968 KB Output is correct
20 Correct 9 ms 27352 KB Output is correct
21 Correct 8 ms 25852 KB Output is correct
22 Correct 8 ms 26200 KB Output is correct
23 Correct 9 ms 26456 KB Output is correct
24 Correct 9 ms 26652 KB Output is correct
25 Correct 110 ms 56100 KB Output is correct
26 Correct 143 ms 72836 KB Output is correct
27 Correct 145 ms 81416 KB Output is correct
28 Correct 164 ms 114248 KB Output is correct
29 Correct 164 ms 94248 KB Output is correct
30 Correct 257 ms 163508 KB Output is correct
31 Correct 360 ms 220768 KB Output is correct
32 Correct 507 ms 302100 KB Output is correct
33 Correct 136 ms 64000 KB Output is correct
34 Correct 182 ms 98784 KB Output is correct
35 Correct 213 ms 124280 KB Output is correct
36 Correct 254 ms 166544 KB Output is correct
37 Correct 155 ms 53412 KB Output is correct
38 Correct 162 ms 72112 KB Output is correct
39 Correct 175 ms 84104 KB Output is correct
40 Correct 205 ms 112700 KB Output is correct
41 Correct 189 ms 98968 KB Output is correct
42 Correct 283 ms 168988 KB Output is correct
43 Correct 390 ms 217756 KB Output is correct
44 Correct 555 ms 304424 KB Output is correct
45 Correct 143 ms 65820 KB Output is correct
46 Correct 191 ms 99848 KB Output is correct
47 Correct 238 ms 126720 KB Output is correct
48 Correct 283 ms 168060 KB Output is correct