oj.uz

Submission #348586

# Submission time Handle Problem Language Result Execution time Memory
348586 2021-01-15T08:59:47 Z Nima_Naderi Klasika (COCI20_klasika) C++14
33 / 110
 565 ms 191712 KB 
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 2e5 + 10;
const ll LOG = 30;
const ll MXM = MXN * LOG + 10;
const ll INF = 1e8;
ll cntr;
int L[MXM], R[MXM], mtm[MXM];
void Pak(ll u = 1, ll bit = LOG - 1){
    mtm[u] = INF;
    if(L[u]) Pak(L[u], bit - 1), L[u] = 0;
    if(R[u]) Pak(R[u], bit - 1), R[u] = 0;
}
void Add(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
    mtm[u] = min(1ll*mtm[u], tm);
    if(bit == -1) return;
    if((val >> bit) & 1LL){
        if(!R[u]) R[u] = cntr ++;
        Add(val, tm, R[u], bit - 1);
    }
    else{
        if(!L[u]) L[u] = cntr ++;
        Add(val, tm, L[u], bit - 1);
    }
}
ll GetMax(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
    if(bit == -1) return 0;
    if((val >> bit) & 1LL){
        if(L[u] && mtm[L[u]] <= tm) return GetMax(val, tm, L[u], bit - 1) + (1LL << bit);
        return GetMax(val, tm, R[u], bit - 1);
    }
    else{
        if(R[u] && mtm[R[u]] <= tm) return GetMax(val, tm, R[u], bit - 1) + (1LL << bit);
        return GetMax(val, tm, L[u], bit - 1);
    }
}
ll n = 1, q, x, y;
ll px[MXN], ANS[MXN];
ll sub[MXN], big[MXN];
vector<pll> adj[MXN];
vector<pair<pll, ll>> Qry, Q[MXN];
string s;
void prep(ll u, ll par){
    sub[u] = 1;
    for(auto Pr : adj[u]){
        ll v, w; tie(v, w) = Pr;
        if(v != par){
            px[v] = px[u] ^ w;
            prep(v, u);
            if(sub[v] > sub[big[u]]) big[u] = v;
            sub[u] += sub[v];
        }
    }
}
void dfs(ll u, ll par){
    Add(px[u], u);
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v != par) dfs(v, u);
    }
}
void DFS(ll u, ll par){
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v == par || v == big[u]) continue;
        DFS(v, u);
        Pak();
    }
    if(big[u]) DFS(big[u], u);
    for(auto Pr : adj[u]){
        ll v = Pr.first;
        if(v == par || v == big[u]) continue;
        dfs(v, u);
    }
    Add(px[u], u);
    for(auto Prr : Q[u]){
        ll val, tm, id = Prr.second;
        tie(val, tm) = Prr.first;
        ANS[id] = GetMax(val, tm);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cntr = 2;
    for(int i = 0; i < MXM; i ++) mtm[i] = INF;
    cin >> q;
    for(int i = 1; i <= q; i ++){
        cin >> s >> x >> y;
        if(s[0] == 'A'){
            ++ n;
            adj[x].push_back({n, y});
            adj[n].push_back({x, y});
        }
        else Qry.push_back({{x, y}, n});
    }
    prep(1, 0);
    for(int i = 0; i < int(Qry.size()); i ++){
        ll a, b, t = Qry[i].second; tie(a, b) = Qry[i].first;
        Q[b].push_back({{px[a], t}, i});
    }
    DFS(1, 0);
    for(int i = 0; i < int(Qry.size()); i ++) cout << ANS[i] << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 24 ms 33260 KB Output is correct
3 Correct 21 ms 33260 KB Output is correct
4 Correct 23 ms 33260 KB Output is correct
5 Correct 26 ms 33320 KB Output is correct
6 Correct 25 ms 33260 KB Output is correct
7 Correct 24 ms 33388 KB Output is correct
8 Correct 22 ms 33388 KB Output is correct
9 Correct 25 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 22 ms 33388 KB Output is correct
12 Correct 21 ms 33292 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 24 ms 33260 KB Output is correct
3 Correct 21 ms 33260 KB Output is correct
4 Correct 23 ms 33260 KB Output is correct
5 Correct 26 ms 33320 KB Output is correct
6 Correct 25 ms 33260 KB Output is correct
7 Correct 24 ms 33388 KB Output is correct
8 Correct 22 ms 33388 KB Output is correct
9 Correct 25 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 22 ms 33388 KB Output is correct
12 Correct 21 ms 33292 KB Output is correct
13 Correct 24 ms 33516 KB Output is correct
14 Correct 24 ms 33644 KB Output is correct
15 Correct 23 ms 33772 KB Output is correct
16 Correct 23 ms 33772 KB Output is correct
17 Correct 23 ms 33644 KB Output is correct
18 Correct 24 ms 33900 KB Output is correct
19 Correct 25 ms 34284 KB Output is correct
20 Correct 26 ms 34540 KB Output is correct
21 Correct 27 ms 33644 KB Output is correct
22 Correct 24 ms 33772 KB Output is correct
23 Correct 24 ms 34028 KB Output is correct
24 Correct 29 ms 34192 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 55276 KB Output is correct
2 Correct 251 ms 62816 KB Output is correct
3 Correct 274 ms 70168 KB Output is correct
4 Correct 283 ms 77460 KB Output is correct
5 Correct 370 ms 80608 KB Output is correct
6 Correct 565 ms 94360 KB Output is correct
7 Runtime error 514 ms 191712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 24 ms 33260 KB Output is correct
3 Correct 21 ms 33260 KB Output is correct
4 Correct 23 ms 33260 KB Output is correct
5 Correct 26 ms 33320 KB Output is correct
6 Correct 25 ms 33260 KB Output is correct
7 Correct 24 ms 33388 KB Output is correct
8 Correct 22 ms 33388 KB Output is correct
9 Correct 25 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 22 ms 33388 KB Output is correct
12 Correct 21 ms 33292 KB Output is correct
13 Correct 24 ms 33516 KB Output is correct
14 Correct 24 ms 33644 KB Output is correct
15 Correct 23 ms 33772 KB Output is correct
16 Correct 23 ms 33772 KB Output is correct
17 Correct 23 ms 33644 KB Output is correct
18 Correct 24 ms 33900 KB Output is correct
19 Correct 25 ms 34284 KB Output is correct
20 Correct 26 ms 34540 KB Output is correct
21 Correct 27 ms 33644 KB Output is correct
22 Correct 24 ms 33772 KB Output is correct
23 Correct 24 ms 34028 KB Output is correct
24 Correct 29 ms 34192 KB Output is correct
25 Correct 227 ms 55276 KB Output is correct
26 Correct 251 ms 62816 KB Output is correct
27 Correct 274 ms 70168 KB Output is correct
28 Correct 283 ms 77460 KB Output is correct
29 Correct 370 ms 80608 KB Output is correct
30 Correct 565 ms 94360 KB Output is correct
31 Runtime error 514 ms 191712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -