oj.uz

Submission #1084770

# Submission time Handle Problem Language Result Execution time Memory
1084770 2024-09-07T00:31:50 Z tfgs Klasika (COCI20_klasika) C++17
33 / 110
 1487 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }

constexpr int p2(int x) { return (int)1 << x; }

const int LOGX = 30, MAX_N = 2e5, MAX_NODES = LOGX*MAX_N;

struct Node {
  int sons[2];
  set<int> tins;
  Node() {
    sons[0] = sons[1] = -1;
    tins = {};
  }
} trie[MAX_NODES];
int trie_siz = 1;

void add_str(int str, int time) {
  int u = 0;
  for (int i = LOGX-1; i >= 0; i--) {
    trie[u].tins.insert(time);
    bool nxt = str&p2(i);
    int& c = trie[u].sons[nxt];
    if (c != -1) {
      u = c;
    } else {
      u = c = trie_siz++;
    }
  }
  trie[u].tins.insert(time);
}

int best_match(int pattern, int l, int r) {
  int match = 0;
  int u = 0;
  for (int i = LOGX-1; i >= 0; i--) {
    bool nxt = !(pattern & p2(i));
    int c = trie[u].sons[nxt];
    if (c != -1 && trie[c].tins.lb(l) != trie[c].tins.end() && *trie[c].tins.lb(l) < r) {
      u = c;
      match += p2(i)*nxt;
    } else {
      u = trie[u].sons[1-nxt];
      match += p2(i)*(1-nxt);
    }
  }
  return match;
}

int timer;
vi tin, tout, x;
V<V<array<int, 2>>> sons;
void dfs(int u) {
  tin[u] = timer++;
  for (auto [v, w] : sons[u]) {
    x[v] = x[u]^w;
    dfs(v);
  }
  tout[u] = timer;
}

void solve() {
  int q; cin >> q;
  int n = 1;

  V<array<int, 3>> queries;
  for (int i = 0; i < q; i++) {
    string typ; cin >> typ;
    if (typ == "Add") {
      int u, w; cin >> u >> w; u--;
      queries.pb({0, n, -1});
      sons.resize(n+1);
      sons[u].pb({n++, w});

    } else {
      int a, b; cin >> a >> b; a--; b--;
      queries.pb({1, a, b});
    }
  }

  tin.resize(n);
  tout.resize(n);
  x.resize(n);
  dfs(0);

  add_str(0, 0);
  for (int i = 0; i < q; i++) {
    if (queries[i][0] == 0) {
      auto [_, u, __] = queries[i];
      add_str(x[u], tin[u]);
    } else {
      auto [_, a, b] = queries[i];
      cout << (x[a]^best_match(x[a], tin[b], tout[b])) << '\n';
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  solve();
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 329236 KB Output is correct
2 Correct 181 ms 329212 KB Output is correct
3 Correct 177 ms 329300 KB Output is correct
4 Correct 178 ms 329552 KB Output is correct
5 Correct 176 ms 329040 KB Output is correct
6 Correct 180 ms 329296 KB Output is correct
7 Correct 174 ms 329292 KB Output is correct
8 Correct 179 ms 329296 KB Output is correct
9 Correct 173 ms 329228 KB Output is correct
10 Correct 178 ms 329304 KB Output is correct
11 Correct 181 ms 329272 KB Output is correct
12 Correct 179 ms 329360 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 329236 KB Output is correct
2 Correct 181 ms 329212 KB Output is correct
3 Correct 177 ms 329300 KB Output is correct
4 Correct 178 ms 329552 KB Output is correct
5 Correct 176 ms 329040 KB Output is correct
6 Correct 180 ms 329296 KB Output is correct
7 Correct 174 ms 329292 KB Output is correct
8 Correct 179 ms 329296 KB Output is correct
9 Correct 173 ms 329228 KB Output is correct
10 Correct 178 ms 329304 KB Output is correct
11 Correct 181 ms 329272 KB Output is correct
12 Correct 179 ms 329360 KB Output is correct
13 Correct 180 ms 329812 KB Output is correct
14 Correct 185 ms 330320 KB Output is correct
15 Correct 172 ms 331088 KB Output is correct
16 Correct 183 ms 331856 KB Output is correct
17 Correct 178 ms 329812 KB Output is correct
18 Correct 181 ms 330348 KB Output is correct
19 Correct 183 ms 331040 KB Output is correct
20 Correct 177 ms 331628 KB Output is correct
21 Correct 176 ms 329632 KB Output is correct
22 Correct 179 ms 330292 KB Output is correct
23 Correct 184 ms 331092 KB Output is correct
24 Correct 179 ms 331480 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 398324 KB Output is correct
2 Correct 1095 ms 461100 KB Output is correct
3 Correct 1487 ms 523324 KB Output is correct
4 Runtime error 1077 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 181 ms 329236 KB Output is correct
2 Correct 181 ms 329212 KB Output is correct
3 Correct 177 ms 329300 KB Output is correct
4 Correct 178 ms 329552 KB Output is correct
5 Correct 176 ms 329040 KB Output is correct
6 Correct 180 ms 329296 KB Output is correct
7 Correct 174 ms 329292 KB Output is correct
8 Correct 179 ms 329296 KB Output is correct
9 Correct 173 ms 329228 KB Output is correct
10 Correct 178 ms 329304 KB Output is correct
11 Correct 181 ms 329272 KB Output is correct
12 Correct 179 ms 329360 KB Output is correct
13 Correct 180 ms 329812 KB Output is correct
14 Correct 185 ms 330320 KB Output is correct
15 Correct 172 ms 331088 KB Output is correct
16 Correct 183 ms 331856 KB Output is correct
17 Correct 178 ms 329812 KB Output is correct
18 Correct 181 ms 330348 KB Output is correct
19 Correct 183 ms 331040 KB Output is correct
20 Correct 177 ms 331628 KB Output is correct
21 Correct 176 ms 329632 KB Output is correct
22 Correct 179 ms 330292 KB Output is correct
23 Correct 184 ms 331092 KB Output is correct
24 Correct 179 ms 331480 KB Output is correct
25 Correct 697 ms 398324 KB Output is correct
26 Correct 1095 ms 461100 KB Output is correct
27 Correct 1487 ms 523324 KB Output is correct
28 Runtime error 1077 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -