oj.uz

Submission #1062214

# Submission time Handle Problem Language Result Execution time Memory
1062214 2024-08-16T21:42:54 Z VMaksimoski008 Klasika (COCI20_klasika) C++17
0 / 110
 80 ms 20444 KB 
#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 = 5e7 + 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=30; 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=30; 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 20444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8284 KB Output isn't correct
2 Halted 0 ms 0 KB -