oj.uz

답안 #647946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647946 2022-10-04T16:49:39 Z LeonaRaging Klasika (COCI20_klasika) C++14
33 / 110
 854 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 = 3e5 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 430156 KB Output is correct
2 Correct 188 ms 430152 KB Output is correct
3 Correct 191 ms 430432 KB Output is correct
4 Correct 209 ms 430348 KB Output is correct
5 Correct 192 ms 430176 KB Output is correct
6 Correct 193 ms 430156 KB Output is correct
7 Correct 207 ms 430200 KB Output is correct
8 Correct 193 ms 430292 KB Output is correct
9 Correct 201 ms 430116 KB Output is correct
10 Correct 205 ms 430144 KB Output is correct
11 Correct 189 ms 430304 KB Output is correct
12 Correct 211 ms 430356 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 430156 KB Output is correct
2 Correct 188 ms 430152 KB Output is correct
3 Correct 191 ms 430432 KB Output is correct
4 Correct 209 ms 430348 KB Output is correct
5 Correct 192 ms 430176 KB Output is correct
6 Correct 193 ms 430156 KB Output is correct
7 Correct 207 ms 430200 KB Output is correct
8 Correct 193 ms 430292 KB Output is correct
9 Correct 201 ms 430116 KB Output is correct
10 Correct 205 ms 430144 KB Output is correct
11 Correct 189 ms 430304 KB Output is correct
12 Correct 211 ms 430356 KB Output is correct
13 Correct 212 ms 430880 KB Output is correct
14 Correct 195 ms 431608 KB Output is correct
15 Correct 225 ms 432304 KB Output is correct
16 Correct 211 ms 432908 KB Output is correct
17 Correct 218 ms 430840 KB Output is correct
18 Correct 226 ms 431424 KB Output is correct
19 Correct 199 ms 432220 KB Output is correct
20 Correct 195 ms 432760 KB Output is correct
21 Correct 217 ms 430796 KB Output is correct
22 Correct 206 ms 431488 KB Output is correct
23 Correct 190 ms 432168 KB Output is correct
24 Correct 198 ms 432820 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 503392 KB Output is correct
2 Runtime error 791 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 430156 KB Output is correct
2 Correct 188 ms 430152 KB Output is correct
3 Correct 191 ms 430432 KB Output is correct
4 Correct 209 ms 430348 KB Output is correct
5 Correct 192 ms 430176 KB Output is correct
6 Correct 193 ms 430156 KB Output is correct
7 Correct 207 ms 430200 KB Output is correct
8 Correct 193 ms 430292 KB Output is correct
9 Correct 201 ms 430116 KB Output is correct
10 Correct 205 ms 430144 KB Output is correct
11 Correct 189 ms 430304 KB Output is correct
12 Correct 211 ms 430356 KB Output is correct
13 Correct 212 ms 430880 KB Output is correct
14 Correct 195 ms 431608 KB Output is correct
15 Correct 225 ms 432304 KB Output is correct
16 Correct 211 ms 432908 KB Output is correct
17 Correct 218 ms 430840 KB Output is correct
18 Correct 226 ms 431424 KB Output is correct
19 Correct 199 ms 432220 KB Output is correct
20 Correct 195 ms 432760 KB Output is correct
21 Correct 217 ms 430796 KB Output is correct
22 Correct 206 ms 431488 KB Output is correct
23 Correct 190 ms 432168 KB Output is correct
24 Correct 198 ms 432820 KB Output is correct
25 Correct 854 ms 503392 KB Output is correct
26 Runtime error 791 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -