oj.uz

Submission #520151

# Submission time Handle Problem Language Result Execution time Memory
520151 2022-01-28T14:44:42 Z HaYoungJoon Klasika (COCI20_klasika) C++17
33 / 110
 1778 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 131 ms 296184 KB Output is correct
2 Correct 140 ms 296324 KB Output is correct
3 Correct 134 ms 296360 KB Output is correct
4 Correct 130 ms 296516 KB Output is correct
5 Correct 132 ms 296276 KB Output is correct
6 Correct 135 ms 296296 KB Output is correct
7 Correct 134 ms 296280 KB Output is correct
8 Correct 154 ms 296432 KB Output is correct
9 Correct 134 ms 296280 KB Output is correct
10 Correct 153 ms 296272 KB Output is correct
11 Correct 130 ms 296396 KB Output is correct
12 Correct 138 ms 296660 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296184 KB Output is correct
2 Correct 140 ms 296324 KB Output is correct
3 Correct 134 ms 296360 KB Output is correct
4 Correct 130 ms 296516 KB Output is correct
5 Correct 132 ms 296276 KB Output is correct
6 Correct 135 ms 296296 KB Output is correct
7 Correct 134 ms 296280 KB Output is correct
8 Correct 154 ms 296432 KB Output is correct
9 Correct 134 ms 296280 KB Output is correct
10 Correct 153 ms 296272 KB Output is correct
11 Correct 130 ms 296396 KB Output is correct
12 Correct 138 ms 296660 KB Output is correct
13 Correct 142 ms 296904 KB Output is correct
14 Correct 145 ms 297640 KB Output is correct
15 Correct 145 ms 298240 KB Output is correct
16 Correct 144 ms 298956 KB Output is correct
17 Correct 134 ms 296912 KB Output is correct
18 Correct 142 ms 297508 KB Output is correct
19 Correct 156 ms 298156 KB Output is correct
20 Correct 145 ms 298752 KB Output is correct
21 Correct 163 ms 296828 KB Output is correct
22 Correct 162 ms 297552 KB Output is correct
23 Correct 142 ms 298232 KB Output is correct
24 Correct 163 ms 298816 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 366704 KB Output is correct
2 Correct 1244 ms 432732 KB Output is correct
3 Correct 1778 ms 497484 KB Output is correct
4 Runtime error 1582 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 131 ms 296184 KB Output is correct
2 Correct 140 ms 296324 KB Output is correct
3 Correct 134 ms 296360 KB Output is correct
4 Correct 130 ms 296516 KB Output is correct
5 Correct 132 ms 296276 KB Output is correct
6 Correct 135 ms 296296 KB Output is correct
7 Correct 134 ms 296280 KB Output is correct
8 Correct 154 ms 296432 KB Output is correct
9 Correct 134 ms 296280 KB Output is correct
10 Correct 153 ms 296272 KB Output is correct
11 Correct 130 ms 296396 KB Output is correct
12 Correct 138 ms 296660 KB Output is correct
13 Correct 142 ms 296904 KB Output is correct
14 Correct 145 ms 297640 KB Output is correct
15 Correct 145 ms 298240 KB Output is correct
16 Correct 144 ms 298956 KB Output is correct
17 Correct 134 ms 296912 KB Output is correct
18 Correct 142 ms 297508 KB Output is correct
19 Correct 156 ms 298156 KB Output is correct
20 Correct 145 ms 298752 KB Output is correct
21 Correct 163 ms 296828 KB Output is correct
22 Correct 162 ms 297552 KB Output is correct
23 Correct 142 ms 298232 KB Output is correct
24 Correct 163 ms 298816 KB Output is correct
25 Correct 768 ms 366704 KB Output is correct
26 Correct 1244 ms 432732 KB Output is correct
27 Correct 1778 ms 497484 KB Output is correct
28 Runtime error 1582 ms 524292 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -