oj.uz

Submission #520144

# Submission time Handle Problem Language Result Execution time Memory
520144 2022-01-28T14:34:06 Z HaYoungJoon Klasika (COCI20_klasika) C++14
0 / 110
 204 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*2];
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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 204 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -