oj.uz

Submission #1084768

# Submission time Handle Problem Language Result Execution time Memory
1084768 2024-09-07T00:28:51 Z tfgs Klasika (COCI20_klasika) C++17
33 / 110
 803 ms 334572 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;
    }
} 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 26 ms 55128 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 24 ms 55388 KB Output is correct
4 Correct 24 ms 55388 KB Output is correct
5 Correct 27 ms 55388 KB Output is correct
6 Correct 24 ms 55132 KB Output is correct
7 Correct 21 ms 55384 KB Output is correct
8 Correct 26 ms 55236 KB Output is correct
9 Correct 24 ms 55132 KB Output is correct
10 Correct 25 ms 55388 KB Output is correct
11 Correct 25 ms 55376 KB Output is correct
12 Correct 24 ms 55444 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55128 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 24 ms 55388 KB Output is correct
4 Correct 24 ms 55388 KB Output is correct
5 Correct 27 ms 55388 KB Output is correct
6 Correct 24 ms 55132 KB Output is correct
7 Correct 21 ms 55384 KB Output is correct
8 Correct 26 ms 55236 KB Output is correct
9 Correct 24 ms 55132 KB Output is correct
10 Correct 25 ms 55388 KB Output is correct
11 Correct 25 ms 55376 KB Output is correct
12 Correct 24 ms 55444 KB Output is correct
13 Correct 27 ms 55900 KB Output is correct
14 Correct 30 ms 56452 KB Output is correct
15 Correct 28 ms 57176 KB Output is correct
16 Correct 35 ms 57632 KB Output is correct
17 Correct 26 ms 55892 KB Output is correct
18 Correct 28 ms 56276 KB Output is correct
19 Correct 26 ms 56916 KB Output is correct
20 Correct 29 ms 57680 KB Output is correct
21 Correct 25 ms 56152 KB Output is correct
22 Correct 28 ms 56332 KB Output is correct
23 Correct 29 ms 56924 KB Output is correct
24 Correct 31 ms 57680 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 124412 KB Output is correct
2 Runtime error 803 ms 334572 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 26 ms 55128 KB Output is correct
2 Correct 30 ms 55120 KB Output is correct
3 Correct 24 ms 55388 KB Output is correct
4 Correct 24 ms 55388 KB Output is correct
5 Correct 27 ms 55388 KB Output is correct
6 Correct 24 ms 55132 KB Output is correct
7 Correct 21 ms 55384 KB Output is correct
8 Correct 26 ms 55236 KB Output is correct
9 Correct 24 ms 55132 KB Output is correct
10 Correct 25 ms 55388 KB Output is correct
11 Correct 25 ms 55376 KB Output is correct
12 Correct 24 ms 55444 KB Output is correct
13 Correct 27 ms 55900 KB Output is correct
14 Correct 30 ms 56452 KB Output is correct
15 Correct 28 ms 57176 KB Output is correct
16 Correct 35 ms 57632 KB Output is correct
17 Correct 26 ms 55892 KB Output is correct
18 Correct 28 ms 56276 KB Output is correct
19 Correct 26 ms 56916 KB Output is correct
20 Correct 29 ms 57680 KB Output is correct
21 Correct 25 ms 56152 KB Output is correct
22 Correct 28 ms 56332 KB Output is correct
23 Correct 29 ms 56924 KB Output is correct
24 Correct 31 ms 57680 KB Output is correct
25 Correct 594 ms 124412 KB Output is correct
26 Runtime error 803 ms 334572 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -