oj.uz

Submission #930133

# Submission time Handle Problem Language Result Execution time Memory
930133 2024-02-18T16:13:51 Z duckindog Klasika (COCI20_klasika) C++17
33 / 110
 1077 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
const int N = 3e5 + 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<vector<int>> 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(vector<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(vector<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";
//  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36188 KB Output is correct
2 Correct 10 ms 36188 KB Output is correct
3 Correct 8 ms 36288 KB Output is correct
4 Correct 8 ms 36444 KB Output is correct
5 Correct 8 ms 36276 KB Output is correct
6 Correct 8 ms 36284 KB Output is correct
7 Correct 9 ms 36444 KB Output is correct
8 Correct 9 ms 36768 KB Output is correct
9 Correct 10 ms 36188 KB Output is correct
10 Correct 9 ms 36520 KB Output is correct
11 Correct 9 ms 36444 KB Output is correct
12 Correct 9 ms 36688 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36188 KB Output is correct
2 Correct 10 ms 36188 KB Output is correct
3 Correct 8 ms 36288 KB Output is correct
4 Correct 8 ms 36444 KB Output is correct
5 Correct 8 ms 36276 KB Output is correct
6 Correct 8 ms 36284 KB Output is correct
7 Correct 9 ms 36444 KB Output is correct
8 Correct 9 ms 36768 KB Output is correct
9 Correct 10 ms 36188 KB Output is correct
10 Correct 9 ms 36520 KB Output is correct
11 Correct 9 ms 36444 KB Output is correct
12 Correct 9 ms 36688 KB Output is correct
13 Correct 11 ms 36956 KB Output is correct
14 Correct 10 ms 37784 KB Output is correct
15 Correct 10 ms 37908 KB Output is correct
16 Correct 11 ms 39444 KB Output is correct
17 Correct 11 ms 37800 KB Output is correct
18 Correct 14 ms 39320 KB Output is correct
19 Correct 16 ms 40920 KB Output is correct
20 Correct 17 ms 41764 KB Output is correct
21 Correct 11 ms 37472 KB Output is correct
22 Correct 13 ms 38548 KB Output is correct
23 Correct 13 ms 39316 KB Output is correct
24 Correct 14 ms 39952 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 96600 KB Output is correct
2 Correct 324 ms 151732 KB Output is correct
3 Correct 366 ms 170652 KB Output is correct
4 Correct 391 ms 262940 KB Output is correct
5 Correct 507 ms 201280 KB Output is correct
6 Correct 899 ms 398636 KB Output is correct
7 Runtime error 1077 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36188 KB Output is correct
2 Correct 10 ms 36188 KB Output is correct
3 Correct 8 ms 36288 KB Output is correct
4 Correct 8 ms 36444 KB Output is correct
5 Correct 8 ms 36276 KB Output is correct
6 Correct 8 ms 36284 KB Output is correct
7 Correct 9 ms 36444 KB Output is correct
8 Correct 9 ms 36768 KB Output is correct
9 Correct 10 ms 36188 KB Output is correct
10 Correct 9 ms 36520 KB Output is correct
11 Correct 9 ms 36444 KB Output is correct
12 Correct 9 ms 36688 KB Output is correct
13 Correct 11 ms 36956 KB Output is correct
14 Correct 10 ms 37784 KB Output is correct
15 Correct 10 ms 37908 KB Output is correct
16 Correct 11 ms 39444 KB Output is correct
17 Correct 11 ms 37800 KB Output is correct
18 Correct 14 ms 39320 KB Output is correct
19 Correct 16 ms 40920 KB Output is correct
20 Correct 17 ms 41764 KB Output is correct
21 Correct 11 ms 37472 KB Output is correct
22 Correct 13 ms 38548 KB Output is correct
23 Correct 13 ms 39316 KB Output is correct
24 Correct 14 ms 39952 KB Output is correct
25 Correct 221 ms 96600 KB Output is correct
26 Correct 324 ms 151732 KB Output is correct
27 Correct 366 ms 170652 KB Output is correct
28 Correct 391 ms 262940 KB Output is correct
29 Correct 507 ms 201280 KB Output is correct
30 Correct 899 ms 398636 KB Output is correct
31 Runtime error 1077 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -