oj.uz

Submission #1084766

# Submission time Handle Problem Language Result Execution time Memory
1084766 2024-09-07T00:16:42 Z tfgs Klasika (COCI20_klasika) C++17
33 / 110
 1351 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 = MAX_N*LOGX;

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(0b10100, 0);
    // add_str(0b11111, 1);
    // ps(best_match(0, 0, 1));
    // return;
    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 129 ms 329040 KB Output is correct
2 Correct 121 ms 329260 KB Output is correct
3 Correct 129 ms 329300 KB Output is correct
4 Correct 130 ms 329420 KB Output is correct
5 Correct 133 ms 329256 KB Output is correct
6 Correct 131 ms 329240 KB Output is correct
7 Correct 131 ms 329304 KB Output is correct
8 Correct 134 ms 329296 KB Output is correct
9 Correct 135 ms 329044 KB Output is correct
10 Correct 142 ms 329156 KB Output is correct
11 Correct 130 ms 329344 KB Output is correct
12 Correct 124 ms 329296 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 329040 KB Output is correct
2 Correct 121 ms 329260 KB Output is correct
3 Correct 129 ms 329300 KB Output is correct
4 Correct 130 ms 329420 KB Output is correct
5 Correct 133 ms 329256 KB Output is correct
6 Correct 131 ms 329240 KB Output is correct
7 Correct 131 ms 329304 KB Output is correct
8 Correct 134 ms 329296 KB Output is correct
9 Correct 135 ms 329044 KB Output is correct
10 Correct 142 ms 329156 KB Output is correct
11 Correct 130 ms 329344 KB Output is correct
12 Correct 124 ms 329296 KB Output is correct
13 Correct 123 ms 329812 KB Output is correct
14 Correct 128 ms 330320 KB Output is correct
15 Correct 131 ms 331160 KB Output is correct
16 Correct 131 ms 331604 KB Output is correct
17 Correct 131 ms 329864 KB Output is correct
18 Correct 132 ms 330324 KB Output is correct
19 Correct 127 ms 331092 KB Output is correct
20 Correct 132 ms 331672 KB Output is correct
21 Correct 134 ms 329792 KB Output is correct
22 Correct 135 ms 330332 KB Output is correct
23 Correct 141 ms 331108 KB Output is correct
24 Correct 143 ms 331608 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 398400 KB Output is correct
2 Correct 1050 ms 461360 KB Output is correct
3 Correct 1351 ms 523328 KB Output is correct
4 Runtime error 997 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 129 ms 329040 KB Output is correct
2 Correct 121 ms 329260 KB Output is correct
3 Correct 129 ms 329300 KB Output is correct
4 Correct 130 ms 329420 KB Output is correct
5 Correct 133 ms 329256 KB Output is correct
6 Correct 131 ms 329240 KB Output is correct
7 Correct 131 ms 329304 KB Output is correct
8 Correct 134 ms 329296 KB Output is correct
9 Correct 135 ms 329044 KB Output is correct
10 Correct 142 ms 329156 KB Output is correct
11 Correct 130 ms 329344 KB Output is correct
12 Correct 124 ms 329296 KB Output is correct
13 Correct 123 ms 329812 KB Output is correct
14 Correct 128 ms 330320 KB Output is correct
15 Correct 131 ms 331160 KB Output is correct
16 Correct 131 ms 331604 KB Output is correct
17 Correct 131 ms 329864 KB Output is correct
18 Correct 132 ms 330324 KB Output is correct
19 Correct 127 ms 331092 KB Output is correct
20 Correct 132 ms 331672 KB Output is correct
21 Correct 134 ms 329792 KB Output is correct
22 Correct 135 ms 330332 KB Output is correct
23 Correct 141 ms 331108 KB Output is correct
24 Correct 143 ms 331608 KB Output is correct
25 Correct 691 ms 398400 KB Output is correct
26 Correct 1050 ms 461360 KB Output is correct
27 Correct 1351 ms 523328 KB Output is correct
28 Runtime error 997 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -