oj.uz

Submission #647936

# Submission time Handle Problem Language Result Execution time Memory
647936 2022-10-04T16:42:19 Z LeonaRaging Klasika (COCI20_klasika) C++14
33 / 110
 191 ms 83800 KB 
#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;
};

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[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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14552 KB Output is correct
3 Correct 9 ms 14660 KB Output is correct
4 Correct 10 ms 14684 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14556 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 9 ms 14612 KB Output is correct
12 Correct 9 ms 14620 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14552 KB Output is correct
3 Correct 9 ms 14660 KB Output is correct
4 Correct 10 ms 14684 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14556 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 9 ms 14612 KB Output is correct
12 Correct 9 ms 14620 KB Output is correct
13 Correct 10 ms 15204 KB Output is correct
14 Correct 12 ms 15960 KB Output is correct
15 Correct 13 ms 16596 KB Output is correct
16 Correct 16 ms 17324 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 12 ms 15764 KB Output is correct
19 Correct 15 ms 16488 KB Output is correct
20 Correct 15 ms 17108 KB Output is correct
21 Correct 11 ms 15152 KB Output is correct
22 Correct 12 ms 15828 KB Output is correct
23 Correct 14 ms 16564 KB Output is correct
24 Correct 15 ms 17108 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 191 ms 83800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14552 KB Output is correct
3 Correct 9 ms 14660 KB Output is correct
4 Correct 10 ms 14684 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14556 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14548 KB Output is correct
11 Correct 9 ms 14612 KB Output is correct
12 Correct 9 ms 14620 KB Output is correct
13 Correct 10 ms 15204 KB Output is correct
14 Correct 12 ms 15960 KB Output is correct
15 Correct 13 ms 16596 KB Output is correct
16 Correct 16 ms 17324 KB Output is correct
17 Correct 11 ms 15188 KB Output is correct
18 Correct 12 ms 15764 KB Output is correct
19 Correct 15 ms 16488 KB Output is correct
20 Correct 15 ms 17108 KB Output is correct
21 Correct 11 ms 15152 KB Output is correct
22 Correct 12 ms 15828 KB Output is correct
23 Correct 14 ms 16564 KB Output is correct
24 Correct 15 ms 17108 KB Output is correct
25 Runtime error 191 ms 83800 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -