oj.uz

Submission #520147

# Submission time Handle Problem Language Result Execution time Memory
520147 2022-01-28T14:38:09 Z HaYoungJoon Klasika (COCI20_klasika) C++14
33 / 110
 1750 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[31*maxn][2];
int dis[maxn],Trietimer = 0, DFStimer = 0;
set<int> StoreTin[31*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 137 ms 296188 KB Output is correct
2 Correct 136 ms 296260 KB Output is correct
3 Correct 143 ms 296332 KB Output is correct
4 Correct 146 ms 296448 KB Output is correct
5 Correct 130 ms 296260 KB Output is correct
6 Correct 150 ms 296316 KB Output is correct
7 Correct 131 ms 296400 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 138 ms 296304 KB Output is correct
10 Correct 132 ms 296248 KB Output is correct
11 Correct 131 ms 296304 KB Output is correct
12 Correct 129 ms 296452 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 296188 KB Output is correct
2 Correct 136 ms 296260 KB Output is correct
3 Correct 143 ms 296332 KB Output is correct
4 Correct 146 ms 296448 KB Output is correct
5 Correct 130 ms 296260 KB Output is correct
6 Correct 150 ms 296316 KB Output is correct
7 Correct 131 ms 296400 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 138 ms 296304 KB Output is correct
10 Correct 132 ms 296248 KB Output is correct
11 Correct 131 ms 296304 KB Output is correct
12 Correct 129 ms 296452 KB Output is correct
13 Correct 143 ms 296892 KB Output is correct
14 Correct 160 ms 297624 KB Output is correct
15 Correct 133 ms 298256 KB Output is correct
16 Correct 141 ms 298948 KB Output is correct
17 Correct 155 ms 296996 KB Output is correct
18 Correct 140 ms 297508 KB Output is correct
19 Correct 141 ms 298180 KB Output is correct
20 Correct 154 ms 298832 KB Output is correct
21 Correct 148 ms 297028 KB Output is correct
22 Correct 131 ms 297572 KB Output is correct
23 Correct 140 ms 298212 KB Output is correct
24 Correct 140 ms 298848 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 366728 KB Output is correct
2 Correct 1222 ms 432736 KB Output is correct
3 Correct 1750 ms 497404 KB Output is correct
4 Runtime error 1492 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 137 ms 296188 KB Output is correct
2 Correct 136 ms 296260 KB Output is correct
3 Correct 143 ms 296332 KB Output is correct
4 Correct 146 ms 296448 KB Output is correct
5 Correct 130 ms 296260 KB Output is correct
6 Correct 150 ms 296316 KB Output is correct
7 Correct 131 ms 296400 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 138 ms 296304 KB Output is correct
10 Correct 132 ms 296248 KB Output is correct
11 Correct 131 ms 296304 KB Output is correct
12 Correct 129 ms 296452 KB Output is correct
13 Correct 143 ms 296892 KB Output is correct
14 Correct 160 ms 297624 KB Output is correct
15 Correct 133 ms 298256 KB Output is correct
16 Correct 141 ms 298948 KB Output is correct
17 Correct 155 ms 296996 KB Output is correct
18 Correct 140 ms 297508 KB Output is correct
19 Correct 141 ms 298180 KB Output is correct
20 Correct 154 ms 298832 KB Output is correct
21 Correct 148 ms 297028 KB Output is correct
22 Correct 131 ms 297572 KB Output is correct
23 Correct 140 ms 298212 KB Output is correct
24 Correct 140 ms 298848 KB Output is correct
25 Correct 771 ms 366728 KB Output is correct
26 Correct 1222 ms 432736 KB Output is correct
27 Correct 1750 ms 497404 KB Output is correct
28 Runtime error 1492 ms 524292 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -