oj.uz

Submission #1084769

# Submission time Handle Problem Language Result Execution time Memory
1084769 2024-09-07T00:30:52 Z tfgs Klasika (COCI20_klasika) C++17
33 / 110
 793 ms 333244 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 = 1e6;

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 33 ms 55120 KB Output is correct
2 Correct 29 ms 55120 KB Output is correct
3 Correct 32 ms 55384 KB Output is correct
4 Correct 32 ms 55384 KB Output is correct
5 Correct 30 ms 55132 KB Output is correct
6 Correct 32 ms 55128 KB Output is correct
7 Correct 36 ms 55376 KB Output is correct
8 Correct 34 ms 55372 KB Output is correct
9 Correct 31 ms 55128 KB Output is correct
10 Correct 32 ms 55380 KB Output is correct
11 Correct 32 ms 55388 KB Output is correct
12 Correct 33 ms 55380 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55120 KB Output is correct
2 Correct 29 ms 55120 KB Output is correct
3 Correct 32 ms 55384 KB Output is correct
4 Correct 32 ms 55384 KB Output is correct
5 Correct 30 ms 55132 KB Output is correct
6 Correct 32 ms 55128 KB Output is correct
7 Correct 36 ms 55376 KB Output is correct
8 Correct 34 ms 55372 KB Output is correct
9 Correct 31 ms 55128 KB Output is correct
10 Correct 32 ms 55380 KB Output is correct
11 Correct 32 ms 55388 KB Output is correct
12 Correct 33 ms 55380 KB Output is correct
13 Correct 34 ms 55888 KB Output is correct
14 Correct 41 ms 56400 KB Output is correct
15 Correct 33 ms 57180 KB Output is correct
16 Correct 36 ms 57684 KB Output is correct
17 Correct 33 ms 55888 KB Output is correct
18 Correct 35 ms 56404 KB Output is correct
19 Correct 37 ms 56916 KB Output is correct
20 Correct 37 ms 57636 KB Output is correct
21 Correct 34 ms 55896 KB Output is correct
22 Correct 35 ms 56340 KB Output is correct
23 Correct 38 ms 56916 KB Output is correct
24 Correct 36 ms 57464 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 123392 KB Output is correct
2 Runtime error 793 ms 333244 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55120 KB Output is correct
2 Correct 29 ms 55120 KB Output is correct
3 Correct 32 ms 55384 KB Output is correct
4 Correct 32 ms 55384 KB Output is correct
5 Correct 30 ms 55132 KB Output is correct
6 Correct 32 ms 55128 KB Output is correct
7 Correct 36 ms 55376 KB Output is correct
8 Correct 34 ms 55372 KB Output is correct
9 Correct 31 ms 55128 KB Output is correct
10 Correct 32 ms 55380 KB Output is correct
11 Correct 32 ms 55388 KB Output is correct
12 Correct 33 ms 55380 KB Output is correct
13 Correct 34 ms 55888 KB Output is correct
14 Correct 41 ms 56400 KB Output is correct
15 Correct 33 ms 57180 KB Output is correct
16 Correct 36 ms 57684 KB Output is correct
17 Correct 33 ms 55888 KB Output is correct
18 Correct 35 ms 56404 KB Output is correct
19 Correct 37 ms 56916 KB Output is correct
20 Correct 37 ms 57636 KB Output is correct
21 Correct 34 ms 55896 KB Output is correct
22 Correct 35 ms 56340 KB Output is correct
23 Correct 38 ms 56916 KB Output is correct
24 Correct 36 ms 57464 KB Output is correct
25 Correct 617 ms 123392 KB Output is correct
26 Runtime error 793 ms 333244 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -