oj.uz

Submission #965504

# Submission time Handle Problem Language Result Execution time Memory
965504 2024-04-18T18:35:06 Z noyancanturk Klasika (COCI20_klasika) C++17
33 / 110
 780 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=2e5+100;
const int mod=1e9+7;
 
using pii=pair<int,int>;

int ans;

vector<bool>lasn;

struct trie{

    struct node{
        node*c[2]{0,0};
    };

    using pnode=node*;
    pnode root;

    trie(){root=new node();}

    void insert(int x){
        pnode cur=root;
        for(int i=29;0<=i;i--){
            if(!cur->c[(x>>i)&1]){
                cur->c[(x>>i)&1]=new node();
            }
            cur=cur->c[(x>>i)&1];
        }
    }

    int search(int x){
        pnode cur=root;
        int ans=0;
        for(int i=29;0<=i;i--){
            if(cur->c[!((x>>i)&1)]){
                if(!((x>>i)&1))ans+=1<<i;
                cur=cur->c[!((x>>i)&1)];
            }else if(cur->c[(x>>i)&1]){
                if((x>>i)&1)ans+=1<<i;
                cur=cur->c[(x>>i)&1];
            }else{
                return 0;
            }
        }
        return ans^x;
    }

};

struct segtree{
    trie tree[4*lim];
    int n;
    segtree(int n):n(n){}
    int P,VAL;
    void update(int l,int r,int node){
        tree[node].insert(VAL);
        if(l==r)return;
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
    }
    void update(int p,int val){
        P=p,VAL=val;
        update(0,n,1);
    }
    int L,R,X;
    int query(int l,int r,int node){
        if(L<=l&&r<=R){
            return tree[node].search(X);
        }
        if(r<L||R<l){
            return 0;
        }
        int mid=(l+r)>>1,child=node<<1;
        return max(query(l,mid,child),query(mid+1,r,child|1));
    }
    int find(int l,int r,int x){
        L=l,R=r,X=x;
        return query(0,n,1);
    }
}*st;

struct qdata{
    int ty,x,y;
};

vector<pii>v[lim];
int dist[lim];
int tin[lim],tout[lim],tt=0;

void dfs(int node){
    tin[node]=tt++;
    for(auto[j,c]:v[node]){
        dist[j]=dist[node]^c;
        dfs(j);
    }
    tout[node]=tt-1;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin); freopen(".out","w",stdout);
#endif
    int n;
    cin>>n;
    qdata q[n];
    int curnode=2;
    for(int i=0;i<n;i++){
        string ty;
        cin>>ty>>q[i].x>>q[i].y;
        if(ty=="Add"){
            q[i].ty=0;
            v[q[i].x].pb({curnode,q[i].y});
            curnode++;
        }else{
            q[i].ty=1;
        }
    }
    dfs(1);
    st=new segtree(n);
    st->update(tin[1],0);
    curnode=2;
    for(int i=0;i<n;i++){
        if(!q[i].ty){
            st->update(tin[curnode],dist[curnode]);
            curnode++;
        }else{
            cout<<st->find(tin[q[i].y],tout[q[i].y],dist[q[i].x])<<"\n";
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39244 KB Output is correct
2 Correct 29 ms 39328 KB Output is correct
3 Correct 26 ms 39860 KB Output is correct
4 Correct 27 ms 40112 KB Output is correct
5 Correct 24 ms 39148 KB Output is correct
6 Correct 33 ms 39336 KB Output is correct
7 Correct 28 ms 39676 KB Output is correct
8 Correct 26 ms 40028 KB Output is correct
9 Correct 37 ms 39288 KB Output is correct
10 Correct 29 ms 39572 KB Output is correct
11 Correct 34 ms 39772 KB Output is correct
12 Correct 34 ms 39956 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39244 KB Output is correct
2 Correct 29 ms 39328 KB Output is correct
3 Correct 26 ms 39860 KB Output is correct
4 Correct 27 ms 40112 KB Output is correct
5 Correct 24 ms 39148 KB Output is correct
6 Correct 33 ms 39336 KB Output is correct
7 Correct 28 ms 39676 KB Output is correct
8 Correct 26 ms 40028 KB Output is correct
9 Correct 37 ms 39288 KB Output is correct
10 Correct 29 ms 39572 KB Output is correct
11 Correct 34 ms 39772 KB Output is correct
12 Correct 34 ms 39956 KB Output is correct
13 Correct 36 ms 42948 KB Output is correct
14 Correct 36 ms 46980 KB Output is correct
15 Correct 36 ms 50784 KB Output is correct
16 Correct 41 ms 54492 KB Output is correct
17 Correct 28 ms 42752 KB Output is correct
18 Correct 33 ms 46672 KB Output is correct
19 Correct 51 ms 50636 KB Output is correct
20 Correct 42 ms 54304 KB Output is correct
21 Correct 30 ms 42848 KB Output is correct
22 Correct 33 ms 46680 KB Output is correct
23 Correct 50 ms 50772 KB Output is correct
24 Correct 38 ms 54096 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 780 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39244 KB Output is correct
2 Correct 29 ms 39328 KB Output is correct
3 Correct 26 ms 39860 KB Output is correct
4 Correct 27 ms 40112 KB Output is correct
5 Correct 24 ms 39148 KB Output is correct
6 Correct 33 ms 39336 KB Output is correct
7 Correct 28 ms 39676 KB Output is correct
8 Correct 26 ms 40028 KB Output is correct
9 Correct 37 ms 39288 KB Output is correct
10 Correct 29 ms 39572 KB Output is correct
11 Correct 34 ms 39772 KB Output is correct
12 Correct 34 ms 39956 KB Output is correct
13 Correct 36 ms 42948 KB Output is correct
14 Correct 36 ms 46980 KB Output is correct
15 Correct 36 ms 50784 KB Output is correct
16 Correct 41 ms 54492 KB Output is correct
17 Correct 28 ms 42752 KB Output is correct
18 Correct 33 ms 46672 KB Output is correct
19 Correct 51 ms 50636 KB Output is correct
20 Correct 42 ms 54304 KB Output is correct
21 Correct 30 ms 42848 KB Output is correct
22 Correct 33 ms 46680 KB Output is correct
23 Correct 50 ms 50772 KB Output is correct
24 Correct 38 ms 54096 KB Output is correct
25 Runtime error 780 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -