oj.uz

Submission #965550

# Submission time Handle Problem Language Result Execution time Memory
965550 2024-04-18T20:54:57 Z noyancanturk Klasika (COCI20_klasika) C++17
33 / 110
 896 ms 520500 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int lim=2e5+500;
const int mod=1e9+7;
const int llim=3e7; 

using pii=pair<int,int>;

struct trie{

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

    static node nds[llim];
    static int nextnode;

    using pnode=node*;
    pnode root;

    trie(){root=nds+(nextnode++);}

    void insert(int x){
        assert(nextnode<llim);
        pnode cur=root;
        for(int i=29;0<=i;i--){
            if(!cur->c[(x>>i)&1]){
                cur->c[(x>>i)&1]=nextnode++;
            }
            cur=nds+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=nds+cur->c[!((x>>i)&1)];
            }else if(cur->c[(x>>i)&1]){
                if((x>>i)&1)ans+=1<<i;
                cur=nds+cur->c[(x>>i)&1];
            }else{
                return 0;
            }
        }
        return ans^x;
    }

};

int trie::nextnode=1;
trie::node trie::nds[llim];

struct segtree{
    trie tree[2*lim];
    int n;
    void update(int p,int val){
        for(p+=n;p;p>>=1)tree[p].insert(val);
    }
    int query(int l,int r,int x){
        int ans=0;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
            if(l&1){
                ans=max(ans,tree[l++].search(x));
            }
            if(r&1){
                ans=max(ans,tree[--r].search(x));
            }
        }
        return ans;
    }
}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){
    //cerr<<node<<"\n";
    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);
    cerr<<sizeof(trie::nds)/1000000<<"\n";
#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.n=tt+50;
    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.query(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 2 ms 12636 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12996 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12728 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12996 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12728 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 5 ms 13660 KB Output is correct
14 Correct 6 ms 14684 KB Output is correct
15 Correct 6 ms 15744 KB Output is correct
16 Correct 7 ms 16788 KB Output is correct
17 Correct 4 ms 13660 KB Output is correct
18 Correct 5 ms 14428 KB Output is correct
19 Correct 5 ms 15708 KB Output is correct
20 Correct 7 ms 16628 KB Output is correct
21 Correct 5 ms 13620 KB Output is correct
22 Correct 6 ms 14684 KB Output is correct
23 Correct 6 ms 15708 KB Output is correct
24 Correct 7 ms 16464 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 141432 KB Output is correct
2 Runtime error 896 ms 520500 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12996 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12728 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 5 ms 13660 KB Output is correct
14 Correct 6 ms 14684 KB Output is correct
15 Correct 6 ms 15744 KB Output is correct
16 Correct 7 ms 16788 KB Output is correct
17 Correct 4 ms 13660 KB Output is correct
18 Correct 5 ms 14428 KB Output is correct
19 Correct 5 ms 15708 KB Output is correct
20 Correct 7 ms 16628 KB Output is correct
21 Correct 5 ms 13620 KB Output is correct
22 Correct 6 ms 14684 KB Output is correct
23 Correct 6 ms 15708 KB Output is correct
24 Correct 7 ms 16464 KB Output is correct
25 Correct 468 ms 141432 KB Output is correct
26 Runtime error 896 ms 520500 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -