oj.uz

Submission #647937

# Submission time Handle Problem Language Result Execution time Memory
647937 2022-10-04T16:42:49 Z LeonaRaging Klasika (COCI20_klasika) C++14
33 / 110
 1903 ms 524288 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[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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 286924 KB Output is correct
2 Correct 130 ms 286860 KB Output is correct
3 Correct 132 ms 287112 KB Output is correct
4 Correct 129 ms 287040 KB Output is correct
5 Correct 131 ms 286864 KB Output is correct
6 Correct 148 ms 286924 KB Output is correct
7 Correct 129 ms 287020 KB Output is correct
8 Correct 127 ms 287044 KB Output is correct
9 Correct 147 ms 287052 KB Output is correct
10 Correct 133 ms 286940 KB Output is correct
11 Correct 126 ms 287048 KB Output is correct
12 Correct 127 ms 287016 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 286924 KB Output is correct
2 Correct 130 ms 286860 KB Output is correct
3 Correct 132 ms 287112 KB Output is correct
4 Correct 129 ms 287040 KB Output is correct
5 Correct 131 ms 286864 KB Output is correct
6 Correct 148 ms 286924 KB Output is correct
7 Correct 129 ms 287020 KB Output is correct
8 Correct 127 ms 287044 KB Output is correct
9 Correct 147 ms 287052 KB Output is correct
10 Correct 133 ms 286940 KB Output is correct
11 Correct 126 ms 287048 KB Output is correct
12 Correct 127 ms 287016 KB Output is correct
13 Correct 135 ms 287564 KB Output is correct
14 Correct 166 ms 288192 KB Output is correct
15 Correct 136 ms 288980 KB Output is correct
16 Correct 129 ms 289612 KB Output is correct
17 Correct 132 ms 287480 KB Output is correct
18 Correct 149 ms 288232 KB Output is correct
19 Correct 146 ms 288936 KB Output is correct
20 Correct 147 ms 289576 KB Output is correct
21 Correct 137 ms 287516 KB Output is correct
22 Correct 140 ms 288204 KB Output is correct
23 Correct 139 ms 288908 KB Output is correct
24 Correct 138 ms 289612 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 360028 KB Output is correct
2 Correct 1352 ms 431044 KB Output is correct
3 Correct 1903 ms 497824 KB Output is correct
4 Runtime error 1694 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 286924 KB Output is correct
2 Correct 130 ms 286860 KB Output is correct
3 Correct 132 ms 287112 KB Output is correct
4 Correct 129 ms 287040 KB Output is correct
5 Correct 131 ms 286864 KB Output is correct
6 Correct 148 ms 286924 KB Output is correct
7 Correct 129 ms 287020 KB Output is correct
8 Correct 127 ms 287044 KB Output is correct
9 Correct 147 ms 287052 KB Output is correct
10 Correct 133 ms 286940 KB Output is correct
11 Correct 126 ms 287048 KB Output is correct
12 Correct 127 ms 287016 KB Output is correct
13 Correct 135 ms 287564 KB Output is correct
14 Correct 166 ms 288192 KB Output is correct
15 Correct 136 ms 288980 KB Output is correct
16 Correct 129 ms 289612 KB Output is correct
17 Correct 132 ms 287480 KB Output is correct
18 Correct 149 ms 288232 KB Output is correct
19 Correct 146 ms 288936 KB Output is correct
20 Correct 147 ms 289576 KB Output is correct
21 Correct 137 ms 287516 KB Output is correct
22 Correct 140 ms 288204 KB Output is correct
23 Correct 139 ms 288908 KB Output is correct
24 Correct 138 ms 289612 KB Output is correct
25 Correct 899 ms 360028 KB Output is correct
26 Correct 1352 ms 431044 KB Output is correct
27 Correct 1903 ms 497824 KB Output is correct
28 Runtime error 1694 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -