제출 #520146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520146		HaYoungJoon	Klasika (COCI20_klasika)	C++14	33 / 110	1756 ms	524292 KiB

klasika

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44