oj.uz

Submission #839137

# Submission time Handle Problem Language Result Execution time Memory
839137 2023-08-28T19:43:18 Z kingmessi Klasika (COCI20_klasika) C++17
33 / 110
 818 ms 357084 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 = 1000001;
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 23 ms 52052 KB Output is correct
2 Correct 26 ms 52052 KB Output is correct
3 Correct 25 ms 52180 KB Output is correct
4 Correct 24 ms 52272 KB Output is correct
5 Correct 24 ms 51988 KB Output is correct
6 Correct 25 ms 52060 KB Output is correct
7 Correct 24 ms 52128 KB Output is correct
8 Correct 24 ms 52300 KB Output is correct
9 Correct 28 ms 52076 KB Output is correct
10 Correct 24 ms 52144 KB Output is correct
11 Correct 24 ms 52184 KB Output is correct
12 Correct 24 ms 52172 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52052 KB Output is correct
2 Correct 26 ms 52052 KB Output is correct
3 Correct 25 ms 52180 KB Output is correct
4 Correct 24 ms 52272 KB Output is correct
5 Correct 24 ms 51988 KB Output is correct
6 Correct 25 ms 52060 KB Output is correct
7 Correct 24 ms 52128 KB Output is correct
8 Correct 24 ms 52300 KB Output is correct
9 Correct 28 ms 52076 KB Output is correct
10 Correct 24 ms 52144 KB Output is correct
11 Correct 24 ms 52184 KB Output is correct
12 Correct 24 ms 52172 KB Output is correct
13 Correct 27 ms 52776 KB Output is correct
14 Correct 27 ms 53452 KB Output is correct
15 Correct 27 ms 54272 KB Output is correct
16 Correct 29 ms 54820 KB Output is correct
17 Correct 27 ms 52712 KB Output is correct
18 Correct 27 ms 53464 KB Output is correct
19 Correct 29 ms 54080 KB Output is correct
20 Correct 30 ms 54792 KB Output is correct
21 Correct 27 ms 52764 KB Output is correct
22 Correct 29 ms 53460 KB Output is correct
23 Correct 30 ms 54160 KB Output is correct
24 Correct 33 ms 54724 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 130504 KB Output is correct
2 Runtime error 818 ms 357084 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52052 KB Output is correct
2 Correct 26 ms 52052 KB Output is correct
3 Correct 25 ms 52180 KB Output is correct
4 Correct 24 ms 52272 KB Output is correct
5 Correct 24 ms 51988 KB Output is correct
6 Correct 25 ms 52060 KB Output is correct
7 Correct 24 ms 52128 KB Output is correct
8 Correct 24 ms 52300 KB Output is correct
9 Correct 28 ms 52076 KB Output is correct
10 Correct 24 ms 52144 KB Output is correct
11 Correct 24 ms 52184 KB Output is correct
12 Correct 24 ms 52172 KB Output is correct
13 Correct 27 ms 52776 KB Output is correct
14 Correct 27 ms 53452 KB Output is correct
15 Correct 27 ms 54272 KB Output is correct
16 Correct 29 ms 54820 KB Output is correct
17 Correct 27 ms 52712 KB Output is correct
18 Correct 27 ms 53464 KB Output is correct
19 Correct 29 ms 54080 KB Output is correct
20 Correct 30 ms 54792 KB Output is correct
21 Correct 27 ms 52764 KB Output is correct
22 Correct 29 ms 53460 KB Output is correct
23 Correct 30 ms 54160 KB Output is correct
24 Correct 33 ms 54724 KB Output is correct
25 Correct 593 ms 130504 KB Output is correct
26 Runtime error 818 ms 357084 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -