oj.uz

Submission #464574

# Submission time Handle Problem Language Result Execution time Memory
464574 2021-08-13T12:58:12 Z TheScrasse Klasika (COCI20_klasika) C++17
33 / 110
 258 ms 96292 KB 
#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 >= 0; i--) {
            k = ((x >> i) & 1);
            tv[s][2] = min(tv[s][2], p);
            if (tv[s][k] == 0) {
                tv[s][k] = tcr; tcr++; tv.pb({0, 0, p});
            }
            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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28620 KB Output is correct
2 Correct 26 ms 28656 KB Output is correct
3 Correct 24 ms 28668 KB Output is correct
4 Correct 25 ms 28756 KB Output is correct
5 Correct 25 ms 28592 KB Output is correct
6 Correct 24 ms 28612 KB Output is correct
7 Correct 26 ms 28748 KB Output is correct
8 Correct 27 ms 28812 KB Output is correct
9 Correct 24 ms 28632 KB Output is correct
10 Correct 25 ms 28768 KB Output is correct
11 Correct 25 ms 28760 KB Output is correct
12 Correct 25 ms 28780 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28620 KB Output is correct
2 Correct 26 ms 28656 KB Output is correct
3 Correct 24 ms 28668 KB Output is correct
4 Correct 25 ms 28756 KB Output is correct
5 Correct 25 ms 28592 KB Output is correct
6 Correct 24 ms 28612 KB Output is correct
7 Correct 26 ms 28748 KB Output is correct
8 Correct 27 ms 28812 KB Output is correct
9 Correct 24 ms 28632 KB Output is correct
10 Correct 25 ms 28768 KB Output is correct
11 Correct 25 ms 28760 KB Output is correct
12 Correct 25 ms 28780 KB Output is correct
13 Correct 26 ms 29448 KB Output is correct
14 Correct 31 ms 30228 KB Output is correct
15 Correct 28 ms 30584 KB Output is correct
16 Correct 29 ms 31608 KB Output is correct
17 Correct 28 ms 29432 KB Output is correct
18 Correct 28 ms 30204 KB Output is correct
19 Correct 30 ms 30808 KB Output is correct
20 Correct 30 ms 31132 KB Output is correct
21 Correct 28 ms 29428 KB Output is correct
22 Correct 28 ms 30272 KB Output is correct
23 Correct 29 ms 30688 KB Output is correct
24 Correct 29 ms 31096 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28620 KB Output is correct
2 Correct 26 ms 28656 KB Output is correct
3 Correct 24 ms 28668 KB Output is correct
4 Correct 25 ms 28756 KB Output is correct
5 Correct 25 ms 28592 KB Output is correct
6 Correct 24 ms 28612 KB Output is correct
7 Correct 26 ms 28748 KB Output is correct
8 Correct 27 ms 28812 KB Output is correct
9 Correct 24 ms 28632 KB Output is correct
10 Correct 25 ms 28768 KB Output is correct
11 Correct 25 ms 28760 KB Output is correct
12 Correct 25 ms 28780 KB Output is correct
13 Correct 26 ms 29448 KB Output is correct
14 Correct 31 ms 30228 KB Output is correct
15 Correct 28 ms 30584 KB Output is correct
16 Correct 29 ms 31608 KB Output is correct
17 Correct 28 ms 29432 KB Output is correct
18 Correct 28 ms 30204 KB Output is correct
19 Correct 30 ms 30808 KB Output is correct
20 Correct 30 ms 31132 KB Output is correct
21 Correct 28 ms 29428 KB Output is correct
22 Correct 28 ms 30272 KB Output is correct
23 Correct 29 ms 30688 KB Output is correct
24 Correct 29 ms 31096 KB Output is correct
25 Incorrect 258 ms 96292 KB Output isn't correct
26 Halted 0 ms 0 KB -