oj.uz

Submission #660592

# Submission time Handle Problem Language Result Execution time Memory
660592 2022-11-22T14:14:48 Z longvu Klasika (COCI20_klasika) C++14
0 / 110
 567 ms 132640 KB 
/**
 *    author:  longvu
 *    created: 11/22/22 20:04:54
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(200901);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

struct Node {
    Node *node_child[2] = {nullptr};
    set<int> memo_idx;
};

#define get_bit(mask, x) (((mask) >> (x)) & 1)

void insert(Node *root, int u, int c) {
    for (int i = 30; i >= 0; --i) {
        if (root -> node_child[get_bit(c, i)] == nullptr) {
            root -> node_child[get_bit(c, i)] = new Node;
        }
        root -> node_child[get_bit(c, i)] -> memo_idx.insert(u);
        root = root -> node_child[get_bit(c, i)];
    }
}

int get(Node *root, int L, int R, int c) {
    int res = 0;
    for (int i = 30; i >= 0; --i) {
        if (root -> node_child[!get_bit(c, i)] != nullptr) {
            if (root -> node_child[!get_bit(c, i)] -> memo_idx.empty()) {
                if (root -> node_child[get_bit(c, i)] == nullptr) {
                    break;
                }
                root = root -> node_child[get_bit(c, i)];
                continue;
            }
            set<int>::iterator l = root -> node_child[!get_bit(c, i)] -> memo_idx.lower_bound(L);
            if (*l >= L && *l <= R) {
                res |= (1 << i);
                root = root -> node_child[!get_bit(c, i)];
            } else {
                if (root -> node_child[get_bit(c, i)] == nullptr) {
                    break;
                }
                root = root -> node_child[get_bit(c, i)];
            }
        } else {
            if (root -> node_child[get_bit(c, i)] == nullptr) {
                break;
            }
            root = root -> node_child[get_bit(c, i)];
        }
    }
    return res;
}

#define Fi first
#define Se second

string TYPE[nax];
int U[nax], V[nax], C[nax], euler[nax], m = 0, fir[nax], subsz[nax], cost[nax];
vector<pair<int, int>> adj[nax];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> q;
    int n = 1;
    for (int i = 1; i <= q; ++i) {
        cin >> TYPE[i] >> U[i] >> C[i];
        if (TYPE[i] == "Add") {
            n++;
            V[i] = n;
            adj[U[i]].push_back({V[i], C[i]});
            adj[V[i]].push_back({U[i], C[i]});
        }
    }
    function<void(int, int)> dfs = [&](int u, int pa) {
        euler[++m] = u;
        fir[u] = m;
        subsz[u] = 1;
        for (auto v : adj[u]) {
            if (v.Fi == pa) {
                continue;
            }
            cost[v.Fi] = v.Se ^ cost[u];
            dfs(v.Fi, u);
            subsz[u] += subsz[v.Fi];
        }
    };
    dfs(1, -1);
    // for (int i = 1; i <= n; ++i) {
    //     cout << euler[i] << " ";
    // }
    // cout << '\n';
    Node *root = new Node();
    for (int i = 1; i <= q; ++i) {
        if (TYPE[i] == "Add") {
            insert(root, fir[V[i]],  cost[V[i]]);
        } else {
            cout << get(root, fir[C[i]], fir[C[i]] + subsz[C[i]] - 1, cost[U[i]]) << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11476 KB Output is correct
2 Incorrect 7 ms 11660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11476 KB Output is correct
2 Incorrect 7 ms 11660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 567 ms 132640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11476 KB Output is correct
2 Incorrect 7 ms 11660 KB Output isn't correct
3 Halted 0 ms 0 KB -