oj.uz

Submission #1063528

# Submission time Handle Problem Language Result Execution time Memory
1063528 2024-08-17T20:00:51 Z VMaksimoski008 Klasika (COCI20_klasika) C++17
0 / 110
 3743 ms 23508 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 = 6e6 + 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;
}

bool anc(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
 
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);
    vector<int> vec;
    for(int i=0; i<q; i++) {
        if(qus[i][0]) vec.push_back(qus[i][1]);
        else {
            int ans = 0;
            for(int &x : vec) {
                if(anc(qus[i][2], x)) ans = max(ans, dist[qus[i][1]] ^ dist[x]);
            }
            cout << ans << '\n';
        }
    }
 
    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

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