oj.uz

Submission #839142

# Submission time Handle Problem Language Result Execution time Memory
839142 2023-08-28T19:47:17 Z kingmessi Klasika (COCI20_klasika) C++17
33 / 110
 1535 ms 524288 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x) 
#define btz(x) __builtin_ctz(x)
using namespace std;

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
  
int power( int N, int M){
    int power = N, sum = 1;
    if(N == 0) sum = 0;
    while(M > 0){if((M & 1) == 1){sum *= power;}
    power = power * power;M = M >> 1;}
    return sum;
}

const int N=200001;
vector<pii> adj[N];
int st[N],en[N],et=0;
int d[N];
 
void dfs(int current,int par){
st[current]=et++;
    for(auto next_vertex : adj[current]){
        if(par == next_vertex.ff)continue;
        d[next_vertex.ff]=d[current]^(next_vertex.ss);
        dfs(next_vertex.ff,current);
    }
en[current]=et;
}

const int SZ = 5800005;
const int MXBIT = 29;
si s[SZ];
int nex[SZ][2],num = 0;
void ins(int node) {
    int x = d[node];
    int cur = 0;
    s[cur].insert(st[node]);
    rrep(i,MXBIT,0) {
        int t = (x>>i)&1;
        if (!nex[cur][t]) {nex[cur][t] = ++num;}
        cur = nex[cur][t];
        s[cur].insert(st[node]);
    }
}

int test(int a,int b) {
    int x = d[a];
    int cur = 0;
    rrep(i,MXBIT,0) {
        int t = ((x>>i)&1)^1;
        if (!nex[cur][t]){
            t^=1;
        }
        else{
            auto it = s[nex[cur][t]].lb(st[b]);
            if(it != s[nex[cur][t]].end()){
                int res = *(it);
                if(res >= en[b])t^=1;
            }
            else t^=1;
        }
        cur = nex[cur][t]; if (t) x ^= 1LL<<i;
    }
    return x;
}



void solve()
{
    vector<pair<string, pii>> qry;
    int node = 1;
    int q;cin>>q;
    rep(i,0,q){
        string op;
        cin>>op;
        int a,b;
        cin>>a>>b;
        qry.pb({op,{a,b}});
        if(op == "Add"){
            node++;
            adj[a].pb({node,b});
        }
    }
    dfs(1,0);
    rep(i,1,node+1)adj[i].clear();
    node = 1;
    ins(1);
    rep(i,0,q){
        string op = qry[i].ff;
        int a = qry[i].ss.ff;
        int b = qry[i].ss.ss;
        if(op == "Add"){
            node++;
            ins(node);
        }
        else{
            int ans = test(a,b);
            // cout<<"ans"<<endl;
            cout<<ans<<'\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
        solve();
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 277564 KB Output is correct
2 Correct 118 ms 277532 KB Output is correct
3 Correct 112 ms 277544 KB Output is correct
4 Correct 109 ms 277752 KB Output is correct
5 Correct 111 ms 277408 KB Output is correct
6 Correct 110 ms 277572 KB Output is correct
7 Correct 110 ms 277624 KB Output is correct
8 Correct 115 ms 277672 KB Output is correct
9 Correct 113 ms 277400 KB Output is correct
10 Correct 114 ms 277584 KB Output is correct
11 Correct 113 ms 277652 KB Output is correct
12 Correct 113 ms 277708 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 277564 KB Output is correct
2 Correct 118 ms 277532 KB Output is correct
3 Correct 112 ms 277544 KB Output is correct
4 Correct 109 ms 277752 KB Output is correct
5 Correct 111 ms 277408 KB Output is correct
6 Correct 110 ms 277572 KB Output is correct
7 Correct 110 ms 277624 KB Output is correct
8 Correct 115 ms 277672 KB Output is correct
9 Correct 113 ms 277400 KB Output is correct
10 Correct 114 ms 277584 KB Output is correct
11 Correct 113 ms 277652 KB Output is correct
12 Correct 113 ms 277708 KB Output is correct
13 Correct 121 ms 278208 KB Output is correct
14 Correct 114 ms 278944 KB Output is correct
15 Correct 114 ms 279632 KB Output is correct
16 Correct 121 ms 280212 KB Output is correct
17 Correct 111 ms 278140 KB Output is correct
18 Correct 111 ms 278796 KB Output is correct
19 Correct 126 ms 279528 KB Output is correct
20 Correct 118 ms 280032 KB Output is correct
21 Correct 110 ms 278152 KB Output is correct
22 Correct 118 ms 278828 KB Output is correct
23 Correct 116 ms 279536 KB Output is correct
24 Correct 122 ms 280144 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 354100 KB Output is correct
2 Correct 1373 ms 420748 KB Output is correct
3 Correct 1535 ms 486064 KB Output is correct
4 Runtime error 1427 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 277564 KB Output is correct
2 Correct 118 ms 277532 KB Output is correct
3 Correct 112 ms 277544 KB Output is correct
4 Correct 109 ms 277752 KB Output is correct
5 Correct 111 ms 277408 KB Output is correct
6 Correct 110 ms 277572 KB Output is correct
7 Correct 110 ms 277624 KB Output is correct
8 Correct 115 ms 277672 KB Output is correct
9 Correct 113 ms 277400 KB Output is correct
10 Correct 114 ms 277584 KB Output is correct
11 Correct 113 ms 277652 KB Output is correct
12 Correct 113 ms 277708 KB Output is correct
13 Correct 121 ms 278208 KB Output is correct
14 Correct 114 ms 278944 KB Output is correct
15 Correct 114 ms 279632 KB Output is correct
16 Correct 121 ms 280212 KB Output is correct
17 Correct 111 ms 278140 KB Output is correct
18 Correct 111 ms 278796 KB Output is correct
19 Correct 126 ms 279528 KB Output is correct
20 Correct 118 ms 280032 KB Output is correct
21 Correct 110 ms 278152 KB Output is correct
22 Correct 118 ms 278828 KB Output is correct
23 Correct 116 ms 279536 KB Output is correct
24 Correct 122 ms 280144 KB Output is correct
25 Correct 676 ms 354100 KB Output is correct
26 Correct 1373 ms 420748 KB Output is correct
27 Correct 1535 ms 486064 KB Output is correct
28 Runtime error 1427 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -