oj.uz

Submission #647938

# Submission time Handle Problem Language Result Execution time Memory
647938 2022-10-04T16:44:27 Z LeonaRaging Klasika (COCI20_klasika) C++14
33 / 110
 1491 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[35 * maxn][2];
    set<int> mySet[35 * 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 157 ms 333892 KB Output is correct
2 Correct 161 ms 333936 KB Output is correct
3 Correct 153 ms 333968 KB Output is correct
4 Correct 155 ms 333980 KB Output is correct
5 Correct 148 ms 333796 KB Output is correct
6 Correct 151 ms 333932 KB Output is correct
7 Correct 151 ms 333960 KB Output is correct
8 Correct 143 ms 334032 KB Output is correct
9 Correct 150 ms 333832 KB Output is correct
10 Correct 144 ms 334044 KB Output is correct
11 Correct 145 ms 333948 KB Output is correct
12 Correct 144 ms 334072 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 333892 KB Output is correct
2 Correct 161 ms 333936 KB Output is correct
3 Correct 153 ms 333968 KB Output is correct
4 Correct 155 ms 333980 KB Output is correct
5 Correct 148 ms 333796 KB Output is correct
6 Correct 151 ms 333932 KB Output is correct
7 Correct 151 ms 333960 KB Output is correct
8 Correct 143 ms 334032 KB Output is correct
9 Correct 150 ms 333832 KB Output is correct
10 Correct 144 ms 334044 KB Output is correct
11 Correct 145 ms 333948 KB Output is correct
12 Correct 144 ms 334072 KB Output is correct
13 Correct 148 ms 334560 KB Output is correct
14 Correct 155 ms 335296 KB Output is correct
15 Correct 150 ms 335952 KB Output is correct
16 Correct 168 ms 336720 KB Output is correct
17 Correct 164 ms 334524 KB Output is correct
18 Correct 149 ms 335096 KB Output is correct
19 Correct 154 ms 335928 KB Output is correct
20 Correct 151 ms 336452 KB Output is correct
21 Correct 153 ms 334428 KB Output is correct
22 Correct 150 ms 335132 KB Output is correct
23 Correct 152 ms 335904 KB Output is correct
24 Correct 154 ms 336520 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 407004 KB Output is correct
2 Correct 1312 ms 474908 KB Output is correct
3 Runtime error 1491 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 333892 KB Output is correct
2 Correct 161 ms 333936 KB Output is correct
3 Correct 153 ms 333968 KB Output is correct
4 Correct 155 ms 333980 KB Output is correct
5 Correct 148 ms 333796 KB Output is correct
6 Correct 151 ms 333932 KB Output is correct
7 Correct 151 ms 333960 KB Output is correct
8 Correct 143 ms 334032 KB Output is correct
9 Correct 150 ms 333832 KB Output is correct
10 Correct 144 ms 334044 KB Output is correct
11 Correct 145 ms 333948 KB Output is correct
12 Correct 144 ms 334072 KB Output is correct
13 Correct 148 ms 334560 KB Output is correct
14 Correct 155 ms 335296 KB Output is correct
15 Correct 150 ms 335952 KB Output is correct
16 Correct 168 ms 336720 KB Output is correct
17 Correct 164 ms 334524 KB Output is correct
18 Correct 149 ms 335096 KB Output is correct
19 Correct 154 ms 335928 KB Output is correct
20 Correct 151 ms 336452 KB Output is correct
21 Correct 153 ms 334428 KB Output is correct
22 Correct 150 ms 335132 KB Output is correct
23 Correct 152 ms 335904 KB Output is correct
24 Correct 154 ms 336520 KB Output is correct
25 Correct 798 ms 407004 KB Output is correct
26 Correct 1312 ms 474908 KB Output is correct
27 Runtime error 1491 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -