oj.uz

Submission #839134

# Submission time Handle Problem Language Result Execution time Memory
839134 2023-08-28T19:35:07 Z kingmessi Klasika (COCI20_klasika) C++17
33 / 110
 1705 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=200005;
vector<pii> adj[N];
int st[N],en[N],et=0;
int d[N];
bool visited[N];
 
void dfs(int current){
st[current]=et++;
visited[current]=true;
    for(auto next_vertex : adj[current]){
        if(visited[next_vertex.ff])continue;
        d[next_vertex.ff]=d[current]^(next_vertex.ss);
        dfs(next_vertex.ff);
    }
en[current]=et;
}

const int SZ = 6000001;
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];
    // cout<<x<<" "<<a<<" "<<b<<endl;
    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;
        // cout<<cur<<"hi"<<endl;
    }
    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);
    // give(d,node+1);cout<<endl;
    // give(st,node+1);cout<<endl;
    // give(en,node+1);cout<<endl;
    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<<endl;
        }
    }
    // cout<<num<<endl;
    // rep(i,0,num+1){
    //     for(auto x : s[i])cout<<x<<" ";cout<<"end"<<endl;
    // }
}

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 127 ms 286868 KB Output is correct
2 Correct 116 ms 286928 KB Output is correct
3 Correct 117 ms 287052 KB Output is correct
4 Correct 117 ms 287072 KB Output is correct
5 Correct 123 ms 286924 KB Output is correct
6 Correct 116 ms 286924 KB Output is correct
7 Correct 121 ms 287060 KB Output is correct
8 Correct 116 ms 287052 KB Output is correct
9 Correct 129 ms 286816 KB Output is correct
10 Correct 122 ms 286920 KB Output is correct
11 Correct 120 ms 287060 KB Output is correct
12 Correct 116 ms 287108 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 286868 KB Output is correct
2 Correct 116 ms 286928 KB Output is correct
3 Correct 117 ms 287052 KB Output is correct
4 Correct 117 ms 287072 KB Output is correct
5 Correct 123 ms 286924 KB Output is correct
6 Correct 116 ms 286924 KB Output is correct
7 Correct 121 ms 287060 KB Output is correct
8 Correct 116 ms 287052 KB Output is correct
9 Correct 129 ms 286816 KB Output is correct
10 Correct 122 ms 286920 KB Output is correct
11 Correct 120 ms 287060 KB Output is correct
12 Correct 116 ms 287108 KB Output is correct
13 Correct 120 ms 287692 KB Output is correct
14 Correct 123 ms 288492 KB Output is correct
15 Correct 123 ms 289288 KB Output is correct
16 Correct 126 ms 289964 KB Output is correct
17 Correct 126 ms 287692 KB Output is correct
18 Correct 121 ms 288436 KB Output is correct
19 Correct 124 ms 289244 KB Output is correct
20 Correct 129 ms 289836 KB Output is correct
21 Correct 122 ms 287736 KB Output is correct
22 Correct 122 ms 288388 KB Output is correct
23 Correct 123 ms 289164 KB Output is correct
24 Correct 125 ms 289876 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 374524 KB Output is correct
2 Correct 1282 ms 447724 KB Output is correct
3 Correct 1705 ms 519012 KB Output is correct
4 Runtime error 1294 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 127 ms 286868 KB Output is correct
2 Correct 116 ms 286928 KB Output is correct
3 Correct 117 ms 287052 KB Output is correct
4 Correct 117 ms 287072 KB Output is correct
5 Correct 123 ms 286924 KB Output is correct
6 Correct 116 ms 286924 KB Output is correct
7 Correct 121 ms 287060 KB Output is correct
8 Correct 116 ms 287052 KB Output is correct
9 Correct 129 ms 286816 KB Output is correct
10 Correct 122 ms 286920 KB Output is correct
11 Correct 120 ms 287060 KB Output is correct
12 Correct 116 ms 287108 KB Output is correct
13 Correct 120 ms 287692 KB Output is correct
14 Correct 123 ms 288492 KB Output is correct
15 Correct 123 ms 289288 KB Output is correct
16 Correct 126 ms 289964 KB Output is correct
17 Correct 126 ms 287692 KB Output is correct
18 Correct 121 ms 288436 KB Output is correct
19 Correct 124 ms 289244 KB Output is correct
20 Correct 129 ms 289836 KB Output is correct
21 Correct 122 ms 287736 KB Output is correct
22 Correct 122 ms 288388 KB Output is correct
23 Correct 123 ms 289164 KB Output is correct
24 Correct 125 ms 289876 KB Output is correct
25 Correct 882 ms 374524 KB Output is correct
26 Correct 1282 ms 447724 KB Output is correct
27 Correct 1705 ms 519012 KB Output is correct
28 Runtime error 1294 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -