oj.uz

Submission #839145

# Submission time Handle Problem Language Result Execution time Memory
839145 2023-08-28T19:48:48 Z kingmessi Klasika (COCI20_klasika) C++17
33 / 110
 1650 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 = 6200005;
const int MXBIT = 30;
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 121 ms 296260 KB Output is correct
2 Correct 119 ms 296364 KB Output is correct
3 Correct 119 ms 296352 KB Output is correct
4 Correct 120 ms 296504 KB Output is correct
5 Correct 120 ms 296196 KB Output is correct
6 Correct 120 ms 296356 KB Output is correct
7 Correct 123 ms 296316 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 119 ms 296228 KB Output is correct
10 Correct 119 ms 296384 KB Output is correct
11 Correct 120 ms 296400 KB Output is correct
12 Correct 119 ms 296484 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 296260 KB Output is correct
2 Correct 119 ms 296364 KB Output is correct
3 Correct 119 ms 296352 KB Output is correct
4 Correct 120 ms 296504 KB Output is correct
5 Correct 120 ms 296196 KB Output is correct
6 Correct 120 ms 296356 KB Output is correct
7 Correct 123 ms 296316 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 119 ms 296228 KB Output is correct
10 Correct 119 ms 296384 KB Output is correct
11 Correct 120 ms 296400 KB Output is correct
12 Correct 119 ms 296484 KB Output is correct
13 Correct 124 ms 297028 KB Output is correct
14 Correct 123 ms 297672 KB Output is correct
15 Correct 124 ms 298468 KB Output is correct
16 Correct 133 ms 299056 KB Output is correct
17 Correct 124 ms 296984 KB Output is correct
18 Correct 126 ms 297580 KB Output is correct
19 Correct 128 ms 298300 KB Output is correct
20 Correct 125 ms 299000 KB Output is correct
21 Correct 121 ms 296988 KB Output is correct
22 Correct 122 ms 297596 KB Output is correct
23 Correct 143 ms 298280 KB Output is correct
24 Correct 127 ms 298916 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 374668 KB Output is correct
2 Correct 1083 ms 443296 KB Output is correct
3 Correct 1650 ms 510368 KB Output is correct
4 Runtime error 1304 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 121 ms 296260 KB Output is correct
2 Correct 119 ms 296364 KB Output is correct
3 Correct 119 ms 296352 KB Output is correct
4 Correct 120 ms 296504 KB Output is correct
5 Correct 120 ms 296196 KB Output is correct
6 Correct 120 ms 296356 KB Output is correct
7 Correct 123 ms 296316 KB Output is correct
8 Correct 129 ms 296448 KB Output is correct
9 Correct 119 ms 296228 KB Output is correct
10 Correct 119 ms 296384 KB Output is correct
11 Correct 120 ms 296400 KB Output is correct
12 Correct 119 ms 296484 KB Output is correct
13 Correct 124 ms 297028 KB Output is correct
14 Correct 123 ms 297672 KB Output is correct
15 Correct 124 ms 298468 KB Output is correct
16 Correct 133 ms 299056 KB Output is correct
17 Correct 124 ms 296984 KB Output is correct
18 Correct 126 ms 297580 KB Output is correct
19 Correct 128 ms 298300 KB Output is correct
20 Correct 125 ms 299000 KB Output is correct
21 Correct 121 ms 296988 KB Output is correct
22 Correct 122 ms 297596 KB Output is correct
23 Correct 143 ms 298280 KB Output is correct
24 Correct 127 ms 298916 KB Output is correct
25 Correct 652 ms 374668 KB Output is correct
26 Correct 1083 ms 443296 KB Output is correct
27 Correct 1650 ms 510368 KB Output is correct
28 Runtime error 1304 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -