oj.uz

Submission #965700

# Submission time Handle Problem Language Result Execution time Memory
965700 2024-04-19T05:41:23 Z noyancanturk Klasika (COCI20_klasika) C++17
110 / 110
 2009 ms 429072 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;

using pii=pair<int,int>;

struct trie{
 
    struct node{
        set<int>st;
        node*c[2]{0,0};
    };
 
    using pnode=node*;
    pnode root;
 
    trie(){root=new node();}
 
    void insert(int x,int y){
        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];
            cur->st.insert(y);
        }
    }
 
    bool check(pnode p,int l,int r){
        if(!p)return 0;
        auto k=p->st.lower_bound(l);
        return k!=p->st.end()&&*k<=r;
    }

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

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);
#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);
    tr.insert(0,0);
    curnode=2;
    for(int i=0;i<n;i++){
        if(!q[i].ty){
            tr.insert(dist[curnode],tin[curnode]);
            curnode++;
        }else{
            cout<<tr.search(dist[q[i].x],tin[q[i].y],tout[q[i].y])<<"\n";
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7956 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7768 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8024 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7956 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7768 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8024 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 4 ms 9052 KB Output is correct
14 Correct 7 ms 10332 KB Output is correct
15 Correct 7 ms 11352 KB Output is correct
16 Correct 7 ms 12888 KB Output is correct
17 Correct 5 ms 8944 KB Output is correct
18 Correct 6 ms 10076 KB Output is correct
19 Correct 8 ms 11356 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 5 ms 8796 KB Output is correct
22 Correct 5 ms 10076 KB Output is correct
23 Correct 6 ms 11500 KB Output is correct
24 Correct 8 ms 12380 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 122820 KB Output is correct
2 Correct 963 ms 229460 KB Output is correct
3 Correct 1155 ms 328784 KB Output is correct
4 Correct 1507 ms 428748 KB Output is correct
5 Correct 484 ms 123980 KB Output is correct
6 Correct 858 ms 225576 KB Output is correct
7 Correct 1245 ms 323368 KB Output is correct
8 Correct 1723 ms 421088 KB Output is correct
9 Correct 468 ms 123632 KB Output is correct
10 Correct 905 ms 226356 KB Output is correct
11 Correct 1139 ms 325488 KB Output is correct
12 Correct 1561 ms 422880 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 3 ms 7956 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 7772 KB Output is correct
6 Correct 2 ms 7768 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8024 KB Output is correct
9 Correct 2 ms 7772 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 4 ms 9052 KB Output is correct
14 Correct 7 ms 10332 KB Output is correct
15 Correct 7 ms 11352 KB Output is correct
16 Correct 7 ms 12888 KB Output is correct
17 Correct 5 ms 8944 KB Output is correct
18 Correct 6 ms 10076 KB Output is correct
19 Correct 8 ms 11356 KB Output is correct
20 Correct 7 ms 12380 KB Output is correct
21 Correct 5 ms 8796 KB Output is correct
22 Correct 5 ms 10076 KB Output is correct
23 Correct 6 ms 11500 KB Output is correct
24 Correct 8 ms 12380 KB Output is correct
25 Correct 503 ms 122820 KB Output is correct
26 Correct 963 ms 229460 KB Output is correct
27 Correct 1155 ms 328784 KB Output is correct
28 Correct 1507 ms 428748 KB Output is correct
29 Correct 484 ms 123980 KB Output is correct
30 Correct 858 ms 225576 KB Output is correct
31 Correct 1245 ms 323368 KB Output is correct
32 Correct 1723 ms 421088 KB Output is correct
33 Correct 468 ms 123632 KB Output is correct
34 Correct 905 ms 226356 KB Output is correct
35 Correct 1139 ms 325488 KB Output is correct
36 Correct 1561 ms 422880 KB Output is correct
37 Correct 891 ms 126804 KB Output is correct
38 Correct 1280 ms 229296 KB Output is correct
39 Correct 1538 ms 331316 KB Output is correct
40 Correct 1955 ms 429072 KB Output is correct
41 Correct 1231 ms 124480 KB Output is correct
42 Correct 1581 ms 225560 KB Output is correct
43 Correct 1759 ms 323412 KB Output is correct
44 Correct 2009 ms 420504 KB Output is correct
45 Correct 1143 ms 123984 KB Output is correct
46 Correct 1609 ms 226708 KB Output is correct
47 Correct 1854 ms 324636 KB Output is correct
48 Correct 1950 ms 422808 KB Output is correct