oj.uz

Submission #520146

# Submission time Handle Problem Language Result Execution time Memory
520146 2022-01-28T14:37:21 Z HaYoungJoon Klasika (COCI20_klasika) C++14
33 / 110
 1756 ms 524292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int maxn = 2*1e5 + 1;
int tin[maxn], tout[maxn], trie[30*maxn][2];
int dis[maxn],Trietimer = 0, DFStimer = 0;
set<int> StoreTin[30*maxn];
vector<pii> adj[maxn];
vector<piii> query;

void DFS(int u) {
    tin[u] = ++DFStimer;
    for (pii i: adj[u]) {
        int v = i.first, w = i.second;
        dis[v] = dis[u] ^ w;
        DFS(v);
    }
    tout[u] = DFStimer;
}

void addNum(int u) {
    int cur = 0;
    for (int i = 30; i >= 0; i--) {
        int val = (dis[u] & (1 << i)) > 0;
        if (!trie[cur][val]) trie[cur][val] = ++Trietimer;
        StoreTin[trie[cur][val]].insert(tin[u]);
        cur = trie[cur][val];
    }
}

int findNum(int u, int toXor) {
    int cur = 0;
    for (int i = 30; i >= 0; i--) {
        int val = (toXor & (1 << i)) > 0;
        auto l = StoreTin[trie[cur][val ^ 1]].lower_bound(tin[u]);
        bool check;
        if (l != StoreTin[trie[cur][val ^ 1]].end() && *l <= tout[u]) check = 1;
        else check = 0;
        if (check) {
            toXor |= (1 << i);
            cur = trie[cur][val ^ 1];
        } else {
            if (val) toXor ^= (1 << i);
            cur = trie[cur][val];
        }
    }
    return toXor;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int Q,x,y;
    cin >> Q;
    string type;
    int cnt = 1;
    for (int i = 1; i <= Q; i++) {
        cin >> type >> x >> y;
        if (type[0] == 'A') {
            adj[x].emplace_back(pii(++cnt,y));
            query.emplace_back(piii(0,pii(cnt,y)));
        } else query.emplace_back(piii(1,pii(x,y)));
    }
    DFS(1);
    addNum(1);
    for (int i = 0; i < query.size(); i++) {
        if (query[i].first == 0) {
            addNum(query[i].second.first);
        } else {
            int res = findNum(query[i].second.second,dis[query[i].second.first]);
            cout << res << '\n';
        }
    }
    return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < query.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 286908 KB Output is correct
2 Correct 128 ms 286912 KB Output is correct
3 Correct 128 ms 286964 KB Output is correct
4 Correct 127 ms 287072 KB Output is correct
5 Correct 130 ms 286892 KB Output is correct
6 Correct 133 ms 286852 KB Output is correct
7 Correct 137 ms 286968 KB Output is correct
8 Correct 127 ms 287192 KB Output is correct
9 Correct 130 ms 286892 KB Output is correct
10 Correct 129 ms 286944 KB Output is correct
11 Correct 142 ms 286948 KB Output is correct
12 Correct 141 ms 286972 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 286908 KB Output is correct
2 Correct 128 ms 286912 KB Output is correct
3 Correct 128 ms 286964 KB Output is correct
4 Correct 127 ms 287072 KB Output is correct
5 Correct 130 ms 286892 KB Output is correct
6 Correct 133 ms 286852 KB Output is correct
7 Correct 137 ms 286968 KB Output is correct
8 Correct 127 ms 287192 KB Output is correct
9 Correct 130 ms 286892 KB Output is correct
10 Correct 129 ms 286944 KB Output is correct
11 Correct 142 ms 286948 KB Output is correct
12 Correct 141 ms 286972 KB Output is correct
13 Correct 132 ms 287456 KB Output is correct
14 Correct 133 ms 288268 KB Output is correct
15 Correct 138 ms 289012 KB Output is correct
16 Correct 136 ms 289468 KB Output is correct
17 Correct 149 ms 287420 KB Output is correct
18 Correct 153 ms 288112 KB Output is correct
19 Correct 135 ms 288832 KB Output is correct
20 Correct 137 ms 289404 KB Output is correct
21 Correct 154 ms 287480 KB Output is correct
22 Correct 134 ms 288132 KB Output is correct
23 Correct 129 ms 288772 KB Output is correct
24 Correct 145 ms 289384 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 357324 KB Output is correct
2 Correct 1273 ms 423456 KB Output is correct
3 Correct 1756 ms 488100 KB Output is correct
4 Runtime error 1744 ms 524292 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 127 ms 286908 KB Output is correct
2 Correct 128 ms 286912 KB Output is correct
3 Correct 128 ms 286964 KB Output is correct
4 Correct 127 ms 287072 KB Output is correct
5 Correct 130 ms 286892 KB Output is correct
6 Correct 133 ms 286852 KB Output is correct
7 Correct 137 ms 286968 KB Output is correct
8 Correct 127 ms 287192 KB Output is correct
9 Correct 130 ms 286892 KB Output is correct
10 Correct 129 ms 286944 KB Output is correct
11 Correct 142 ms 286948 KB Output is correct
12 Correct 141 ms 286972 KB Output is correct
13 Correct 132 ms 287456 KB Output is correct
14 Correct 133 ms 288268 KB Output is correct
15 Correct 138 ms 289012 KB Output is correct
16 Correct 136 ms 289468 KB Output is correct
17 Correct 149 ms 287420 KB Output is correct
18 Correct 153 ms 288112 KB Output is correct
19 Correct 135 ms 288832 KB Output is correct
20 Correct 137 ms 289404 KB Output is correct
21 Correct 154 ms 287480 KB Output is correct
22 Correct 134 ms 288132 KB Output is correct
23 Correct 129 ms 288772 KB Output is correct
24 Correct 145 ms 289384 KB Output is correct
25 Correct 768 ms 357324 KB Output is correct
26 Correct 1273 ms 423456 KB Output is correct
27 Correct 1756 ms 488100 KB Output is correct
28 Runtime error 1744 ms 524292 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -