Submission #647941

#	Time	Username	Problem	Language	Result	Execution time	Memory
647941		LeonaRaging	Klasika (COCI20_klasika)	C++14	0 / 110	215 ms	524288 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 = 1e6 + 4;
const int INF = 1e9;
const int LOG = 30;
 
struct Query {
    int t, u, v, idx;
};
 
int n, q, tin[maxn], tout[maxn], dis[maxn];
vector<pair<int,int>> adj[maxn];
vector<Query> queries;
 
struct Trie {
    int num, nxt[30 * maxn][2];
    set<int> mySet[30 * maxn];
    void add(int u) {
        int v = 0;
        for (int i = LOG; i >= 0; i--) {
            mySet[v].insert(tin[u]);
            int c = (dis[u] >> i & 1);
            if (!nxt[v][c]) {
                nxt[v][c] = ++num;
            }
            v = nxt[v][c];
        }
        mySet[v].insert(tin[u]);
    }
    bool ok(int u, int v) {
        auto lo = mySet[v].lower_bound(tin[u]);
        if (lo == mySet[v].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 (nxt[v][c] && ok(u, nxt[v][c])) {
                v = nxt[v][c];
                res += (1 << i);
            }
            else if (nxt[v][c ^ 1] && ok(u, nxt[v][c ^ 1]))
                v = nxt[v][c ^ 1];
            else break;
        }
        return res;
    }
} t;
 
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);
    t.add(1);
    for (auto it : queries) {
        int type = it.t, u = it.u, v = it.v;
        if (type == 0) t.add(v);
        else cout << t.get(dis[u], v) << '\n';
    }
}

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