oj.uz

Submission #520142

# Submission time Handle Problem Language Result Execution time Memory
520142 2022-01-28T14:33:17 Z HaYoungJoon Klasika (COCI20_klasika) C++14
33 / 110
 1729 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];
    }
  //  StoreTin[cur].insert(tin[u]);
}

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:70: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]
   70 |     for (int i = 0; i < query.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 286888 KB Output is correct
2 Correct 132 ms 286948 KB Output is correct
3 Correct 123 ms 287028 KB Output is correct
4 Correct 124 ms 286980 KB Output is correct
5 Correct 127 ms 286800 KB Output is correct
6 Correct 124 ms 286940 KB Output is correct
7 Correct 141 ms 287016 KB Output is correct
8 Correct 126 ms 287080 KB Output is correct
9 Correct 125 ms 286872 KB Output is correct
10 Correct 130 ms 286940 KB Output is correct
11 Correct 135 ms 287028 KB Output is correct
12 Correct 131 ms 287040 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 286888 KB Output is correct
2 Correct 132 ms 286948 KB Output is correct
3 Correct 123 ms 287028 KB Output is correct
4 Correct 124 ms 286980 KB Output is correct
5 Correct 127 ms 286800 KB Output is correct
6 Correct 124 ms 286940 KB Output is correct
7 Correct 141 ms 287016 KB Output is correct
8 Correct 126 ms 287080 KB Output is correct
9 Correct 125 ms 286872 KB Output is correct
10 Correct 130 ms 286940 KB Output is correct
11 Correct 135 ms 287028 KB Output is correct
12 Correct 131 ms 287040 KB Output is correct
13 Correct 127 ms 287576 KB Output is correct
14 Correct 139 ms 288188 KB Output is correct
15 Correct 133 ms 288880 KB Output is correct
16 Correct 130 ms 289548 KB Output is correct
17 Correct 130 ms 287440 KB Output is correct
18 Correct 141 ms 288100 KB Output is correct
19 Correct 133 ms 288836 KB Output is correct
20 Correct 132 ms 289412 KB Output is correct
21 Correct 135 ms 287520 KB Output is correct
22 Correct 142 ms 288140 KB Output is correct
23 Correct 129 ms 288844 KB Output is correct
24 Correct 134 ms 289496 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 360196 KB Output is correct
2 Correct 1290 ms 426620 KB Output is correct
3 Correct 1729 ms 491400 KB Output is correct
4 Runtime error 1640 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 134 ms 286888 KB Output is correct
2 Correct 132 ms 286948 KB Output is correct
3 Correct 123 ms 287028 KB Output is correct
4 Correct 124 ms 286980 KB Output is correct
5 Correct 127 ms 286800 KB Output is correct
6 Correct 124 ms 286940 KB Output is correct
7 Correct 141 ms 287016 KB Output is correct
8 Correct 126 ms 287080 KB Output is correct
9 Correct 125 ms 286872 KB Output is correct
10 Correct 130 ms 286940 KB Output is correct
11 Correct 135 ms 287028 KB Output is correct
12 Correct 131 ms 287040 KB Output is correct
13 Correct 127 ms 287576 KB Output is correct
14 Correct 139 ms 288188 KB Output is correct
15 Correct 133 ms 288880 KB Output is correct
16 Correct 130 ms 289548 KB Output is correct
17 Correct 130 ms 287440 KB Output is correct
18 Correct 141 ms 288100 KB Output is correct
19 Correct 133 ms 288836 KB Output is correct
20 Correct 132 ms 289412 KB Output is correct
21 Correct 135 ms 287520 KB Output is correct
22 Correct 142 ms 288140 KB Output is correct
23 Correct 129 ms 288844 KB Output is correct
24 Correct 134 ms 289496 KB Output is correct
25 Correct 734 ms 360196 KB Output is correct
26 Correct 1290 ms 426620 KB Output is correct
27 Correct 1729 ms 491400 KB Output is correct
28 Runtime error 1640 ms 524292 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -