Submission #1062213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062213		VMaksimoski008	Klasika (COCI20_klasika)	C++17	0 / 110	99 ms	23288 KiB

klasika

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e7 + 5;
const int M = 2e5 + 5;

int trie[maxn][2], id=1, in[M], out[M], timer=0;
vector<ll> dist(M);
vector<pii> graph[M];

void dfs(int u) {
    in[u] = timer++;
    for(auto &[v, w] : graph[u]) {
        dist[v] = dist[u] ^ w;
        dfs(v);
    }
    out[u] = timer;
}

void insert(ll x) {
    int u = 0;
    for(int i=60; i>=0; i--) {
        bool b = x & (1ll << i);
        if(!trie[u][b]) trie[u][b] = id++;
        u = trie[u][b];
    }
}

ll XOR(ll x) {
    int u = 0;
    ll ans = 0;
    for(int i=60; i>=0; i--) {
        bool b = x & (1ll << i);
        if(trie[u][!b]) ans |= (1ll << i), u = trie[u][!b];
        else u = trie[u][b];
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int q, n=1;
    cin >> q;

    vector<array<int, 3> > qus;
    for(int i=0; i<q; i++) {
        string s;
        int a, b;
        cin >> s >> a >> b;
        qus.push_back({ (s[0] == 'A'), (s[0] == 'A' ? n + 1 : a), b });
        if(s[0] == 'A') graph[a].push_back({ ++n, b });
    }

    dfs(1);

    for(int i=0; i<q; i++) {
        if(qus[i][0]) insert(dist[qus[i][1]]);
        if(!qus[i][0]) cout << XOR(dist[qus[i][1]]) << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44