oj.uz

Submission #770091

# Submission time Handle Problem Language Result Execution time Memory
770091 2023-06-30T18:25:26 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 5000 ms 171420 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

const int lg = 31;

struct Trie {
  public:
  vector<vector<int>> trie;
  vector<int> values;
  unordered_map<int, bool> used;

  Trie() {
    trie.push_back(vector<int> (2, -1));
  };

  void add(int x) {
    if (used[x]) {
      return ;
    }
    used[x] = true;
    values.push_back(x);
    int t = 0;
    for (int i = lg - 1; i >= 0; i--) {
      int bit = (x >> i) & 1;

      if (trie[t][bit] == -1) {
        trie[t][bit] = (int) trie.size();
        trie.emplace_back(2, -1);
      }
      t = trie[t][bit];
    }
  }

  int get(int x) {
    int t = 0;
    int ret = 0;

    for (int i = lg - 1; i >= 0; i--) {
      int bit = (x >> i) & 1;
      bit ^= 1;

      if (trie[t][bit] == -1) {
        bit ^= 1;
      } else {
        ret |= (1 << i);
      }

      if (trie[t][bit] == -1) {
        return 0;
      }
      t = trie[t][bit];
    }
    return ret;
  };
};

Trie Merge(Trie a, Trie b) {
  Trie c;

  if ((int) a.values.size() > (int) b.values.size()) {
    swap(a.values, b.values);
    swap(a.trie, b.trie);
    swap(a.used, b.used);
  }
  c.values = b.values;
  c.trie = b.trie;
  c.used = b.used;

  for (int i = 0; i < (int) a.values.size(); i++) {
    c.add(a.values[i]);
  }
  return c;
}

class segTree {
  public:
  int n;
  vector<Trie> st;

  segTree(int _n) : n(_n) {
    st.resize(n * 4);
  }

  void update(int v, int l, int r, int pos, int nv) {
    if (l == r) {
      st[v].add(nv);
      return ;
    }

    int mid = l + (r - l) / 2;
    if (pos <= mid) {
      update(v * 2, l, mid, pos, nv);
    } else {
      update(v * 2 + 1, mid + 1, r, pos, nv);
    }
    st[v] = Merge(st[v * 2], st[v * 2 + 1]);
  }

  int get(int v, int l, int r, int low, int high, int p) {
    if (l == low && r == high) {
      return st[v].get(p);
    }

    int mid = l + (r - l) / 2;
    if (high <= mid) {
      return get(v * 2, l, mid, low, high, p);
    } else if (low > mid) {
      return get(v * 2 + 1, mid + 1, r, low, high, p);
    } else {
      return max(get(v * 2, l, mid, low, mid, p),
            get(v * 2 + 1, mid + 1, r, mid + 1, high, p));
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int q;
  cin >> q;

  int n = q + 1;

  vector<vector<int>> adj(n);
  vector<int> pref(n);

  auto Add = [&](int x, int y, int w) {
    adj[x].push_back(y);
    pref[y] = pref[x] ^ w;
  };

  int cnt = 1;

  vector<array<int, 3>> queries;

  for (int i = 0; i < q; i++) {
    string type;
    cin >> type;

    if (type == "Add") {
      int x, w;
      cin >> x >> w;
      --x;
      Add(x, cnt, w);
      queries.push_back({1, cnt, 0});
      ++cnt;

    } else {
      int a, b;
      cin >> a >> b;
      --a, --b;

      queries.push_back({2, a, b});
    }
  }

  vector<int> in(n);
  vector<int> out(n);
  vector<int> euler_tour;

  function<void(int)> Dfs = [&](int u) {
    in[u] = (int) euler_tour.size();
    euler_tour.push_back(u);

    for (auto v : adj[u]) {
      Dfs(v);
    }

    out[u] = (int) euler_tour.size() - 1;
  };

  Dfs(0);

  segTree st(n);

  st.update(1, 0, n - 1, in[0], 0);

  for (int i = 0; i < (int) queries.size(); i++) {
    int type = queries[i][0];
    
    if (type == 1) {
      int u = queries[i][1];

      st.update(1, 0, n - 1, in[u], pref[u]);
    } else {
      int a = queries[i][1];
      int b = queries[i][2];

      cout << st.get(1, 0, n - 1, in[b], out[b], pref[a]) << '\n';
    }
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1364 KB Output is correct
2 Correct 26 ms 1796 KB Output is correct
3 Correct 38 ms 2640 KB Output is correct
4 Correct 58 ms 3224 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 20 ms 1816 KB Output is correct
7 Correct 35 ms 2600 KB Output is correct
8 Correct 59 ms 3440 KB Output is correct
9 Correct 11 ms 1252 KB Output is correct
10 Correct 27 ms 2124 KB Output is correct
11 Correct 45 ms 2896 KB Output is correct
12 Correct 56 ms 3392 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1364 KB Output is correct
2 Correct 26 ms 1796 KB Output is correct
3 Correct 38 ms 2640 KB Output is correct
4 Correct 58 ms 3224 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 20 ms 1816 KB Output is correct
7 Correct 35 ms 2600 KB Output is correct
8 Correct 59 ms 3440 KB Output is correct
9 Correct 11 ms 1252 KB Output is correct
10 Correct 27 ms 2124 KB Output is correct
11 Correct 45 ms 2896 KB Output is correct
12 Correct 56 ms 3392 KB Output is correct
13 Correct 616 ms 11424 KB Output is correct
14 Correct 1791 ms 20564 KB Output is correct
15 Correct 3057 ms 28932 KB Output is correct
16 Correct 4472 ms 36880 KB Output is correct
17 Correct 619 ms 11372 KB Output is correct
18 Correct 1804 ms 20400 KB Output is correct
19 Correct 3337 ms 30956 KB Output is correct
20 Correct 4963 ms 39244 KB Output is correct
21 Correct 616 ms 11080 KB Output is correct
22 Correct 1752 ms 20036 KB Output is correct
23 Correct 3099 ms 29668 KB Output is correct
24 Correct 4645 ms 38000 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 171420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1364 KB Output is correct
2 Correct 26 ms 1796 KB Output is correct
3 Correct 38 ms 2640 KB Output is correct
4 Correct 58 ms 3224 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 20 ms 1816 KB Output is correct
7 Correct 35 ms 2600 KB Output is correct
8 Correct 59 ms 3440 KB Output is correct
9 Correct 11 ms 1252 KB Output is correct
10 Correct 27 ms 2124 KB Output is correct
11 Correct 45 ms 2896 KB Output is correct
12 Correct 56 ms 3392 KB Output is correct
13 Correct 616 ms 11424 KB Output is correct
14 Correct 1791 ms 20564 KB Output is correct
15 Correct 3057 ms 28932 KB Output is correct
16 Correct 4472 ms 36880 KB Output is correct
17 Correct 619 ms 11372 KB Output is correct
18 Correct 1804 ms 20400 KB Output is correct
19 Correct 3337 ms 30956 KB Output is correct
20 Correct 4963 ms 39244 KB Output is correct
21 Correct 616 ms 11080 KB Output is correct
22 Correct 1752 ms 20036 KB Output is correct
23 Correct 3099 ms 29668 KB Output is correct
24 Correct 4645 ms 38000 KB Output is correct
25 Execution timed out 5037 ms 171420 KB Time limit exceeded
26 Halted 0 ms 0 KB -