Submission #464588

#	Time	Username	Problem	Language	Result	Execution time	Memory
464588		TheScrasse	Klasika (COCI20_klasika)	C++17	110 / 110	993 ms	304524 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 200010

struct trie {
    vector<array<ll, 2>> ta;
    vector<array<ll, 3>> tv;
    ll tcr, td;

    trie(): ta({}), tv({{0, 0, 0}}), tcr(1), td(0) {}

    void ins(ll p, ll x) {
        ll i, k, s = 0;
        ta.pb({p, x});
        for (i = 30; i >= -1; i--) {
            tv[s][2] = min(tv[s][2], p);
            if (i == -1) continue;
            k = ((x >> i) & 1);
            if (tv[s][k] == 0) {
                tv[s][k] = tcr; tcr++; tv.pb({0, 0, INF});
            }
            s = tv[s][k];
        }
    }

    ll find_max(ll x, ll m) {
        // cout << "find_max " << x _ m << nl;
        ll i, k, s = 0, r = 0;
        for (i = 30; i >= 0; i--) {
            k = ((x >> i) & 1);
            if (tv[s][k ^ 1] != 0 && tv[tv[s][k ^ 1]][2] <= m) {
                s = tv[s][k ^ 1]; r += (1 << i);
            } else {
                s = tv[s][k];
            }
        }
        return r;
    }
};

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll cr, pr[maxn], dp[maxn], q;
bool vis[maxn];
string s;
vector<array<ll, 2>> rs;
vector<array<ll, 2>> adj[maxn];
vector<array<ll, 3>> qdj[maxn];
trie tr[maxn];

void onion(ll a, ll b, ll d) { // (a, b) = (high, low)
    if (tr[a].ta.size() < tr[b].ta.size()) {
        swap(tr[a], tr[b]); tr[a].td ^= d; tr[b].td ^= d;
    }
    for (auto [p, x] : tr[b].ta) tr[a].ins(p, x ^ d ^ tr[a].td ^ tr[b].td);
    tr[b] = trie();
}

void dfs(ll s) {
    for (auto [u, w] : adj[s]) {
        dp[u] = dp[s] ^ w;
        dfs(u);
    }
}

void sml(ll s) {
    for (auto [u, w] : adj[s]) {
        sml(u);
        onion(s, u, w);
    }

    for (auto [u, m, t] : qdj[s]) {
        rs.pb({t, tr[s].find_max(dp[s] ^ dp[u] ^ tr[s].td, m)});
    }

    /* cout << "dbg trie " << s << nl;
    for (auto u : tr[s].ta) cout << u[0] _ u[1] << nl;
    for (auto u : tr[s].tv) cout << u[0] _ u[1] _ u[2] << nl;
    cout << "tcr = " << tr[s].tcr << nl;
    cout << "td = " << tr[s].td << nl;
    cout << nl; */
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> q; cr = 2;
    for (i = 1; i <= q; i++) {
        cin >> s >> a >> b;
        if (s[0] == 'A') {
            adj[a].pb({cr, b}); cr++; // directed?
        } else {
            qdj[b].pb({a, cr - 1, i});
        }
    }

    n = cr - 1;
    for (i = 1; i <= n; i++) tr[i].ins(i, 0);

    dfs(1); sml(1);

    sort(rs.begin(), rs.end());
    for (auto [cr, u] : rs) cout << u << nl;

    return 0;
}

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