Submission #647960

#	Time	Username	Problem	Language	Result	Execution time	Memory
647960		LeonaRaging	Klasika (COCI20_klasika)	C++14	110 / 110	3650 ms	483312 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
 
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 4;
const int INF = 1e9;
const int LOG = 30;
 
struct Query {
    int t, u, v, idx;
};
 
struct Node {
    int nxt[2];
    set<int> mySet;
    Node() {
        nxt[0] = nxt[1] = 0;
    }
};

int n, q, tin[maxn], tout[maxn], dis[maxn];
vector<pair<int,int>> adj[maxn];
vector<Query> queries;
vector<Node> t(1); 

void add(int u) {
    int v = 0;
    for (int i = LOG; i >= 0; i--) {
        t[v].mySet.insert(tin[u]);
        int c = (dis[u] >> i & 1);
        if (!t[v].nxt[c]) {
            t[v].nxt[c] = t.size();
            t.emplace_back();
        }
        v = t[v].nxt[c];
    }
    t[v].mySet.insert(tin[u]);
}

bool ok(int u, int v) {
    auto lo = t[v].mySet.lower_bound(tin[u]);
    if (lo == t[v].mySet.end() || *lo > tout[u]) return 0;
    return 1;
}

int get(int x, int u) {
    int v = 0, res = 0;
    for (int i = LOG; i >= 0; i--) {
        int c = (x >> i & 1) ^ 1;
        if (t[v].nxt[c] && ok(u, t[v].nxt[c])) {
            v = t[v].nxt[c];
            res += (1 << i);
        }
        else if (t[v].nxt[c ^ 1] && ok(u, t[v].nxt[c ^ 1]))
            v = t[v].nxt[c ^ 1];
        else break;
    }
    return res;
}

 
void dfs(int u) {
    tin[u] = ++tin[0];
    for (auto it : adj[u]) {
        int v, w; tie(v, w) = it;
        dis[v] = dis[u] ^ w;
        dfs(v);
    }
    tout[u] = tin[0];
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> q;
    n = 1;
    for (int i = 1; i <= q; i++) {
        string type; int u, v;
        cin >> type >> u >> v;
        if (type == "Add")
            adj[u].pb({++n, v});
        if (type == "Add")
            queries.pb({0, u, n, i});
        else queries.pb({1, u, v, i});
    }
    dfs(1);
    add(1);
    for (auto it : queries) {
        int type = it.t, u = it.u, v = it.v;
        if (type == 0) add(v);
        else cout << get(dis[u], v) << '\n';
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44