oj.uz

Submission #211218

# Submission time Handle Problem Language Result Execution time Memory
211218 2020-03-19T13:44:15 Z sm1ley Klasika (COCI20_klasika) C++17
110 / 110
 3795 ms 451980 KB 
#include <vector>
#include <set>
#include <iostream>
#include <bitset>
#define ll long long
#define endl "\n"
#define IOS cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;

const int N = 2e5+13;
struct Query{
    int t,x,y;
};
struct Node{
    set<int> times;
    Node *bit[2];
    Node(){
        bit[0]=bit[1]=NULL;
    }
};
Node trie;

int timer;
int tin[N], tout[N];
int xr[N]; //distance from node 1 to node i
vector<pair<int,int>> g[N];
vector<Query> question;

void dfs(int v,int p,int val){
    tin[v]=++timer;
    xr[v]=xr[p]^val;
    for(auto t:g[v]){
        if(t.first==p)continue;
        dfs(t.first,v,t.second);
    }
    tout[v]=timer;//++;
}

void insert(int val,int num){
    Node *t = &trie;
    for(int i=30;i>=-1;i--){
        t->times.insert(num);
        if(val&(1<<i)){
            if(t->bit[1]==NULL)t->bit[1]=new Node();
            t = t->bit[1];
        }else{
            if(t->bit[0]==NULL)t->bit[0]=new Node();
            t = t->bit[0];
        }
    }
}
bool can(set<int> &a,int in,int out){
    return a.lower_bound(in)==a.upper_bound(out);
}

//
void get(int val,int in,int out){
    Node *t = &trie;
    int ans = 0;

    for(int i=30;i>=0;i--){
        //if(t->bit[1]==NULL)t->bit[1]=new Node();
        //if(t->bit[0]==NULL)t->bit[0]=new Node();
        if(val&(1<<i)){//ned 0
            if(t->bit[0]==NULL || can(t->bit[0]->times,in,out)){
                t = t->bit[1];
            }else{
                t = t->bit[0];
                ans |= (1<<i);
            }
        }
        else{ //ned 1
            if(t->bit[1]==NULL||can(t->bit[1]->times,in,out)){
                t = t->bit[0];
            }else{
                ans |= (1<<i);
                t = t->bit[1];
            }
        }
        //cout<<bitset<10>(ans)<<endl;
    }
    cout<<ans<<endl;
}

int q;
int main(){
    //IOS;
    cin>>q;
    int num=2;
    for(int i=0;i<q;i++){
        string s;cin>>s;
        int a,b;cin>>a>>b;
        if(s=="Add"){
            question.push_back({1,num,a});
            g[a].push_back({num,b});
            g[num].push_back({a,b});
            num++;
        }
        if(s=="Query")question.push_back({2,a,b});
    }
    dfs(1,1,0);
    insert(0,tin[1]);
    for(int i=0;i<q;i++){
        int t=question[i].t;
        int x=question[i].x;
        int y=question[i].y;
        if(t==1) insert(xr[x],tin[x]);    
        else get(xr[x],tin[y],tout[y]);
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5376 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5376 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct
13 Correct 12 ms 6528 KB Output is correct
14 Correct 16 ms 7808 KB Output is correct
15 Correct 18 ms 9088 KB Output is correct
16 Correct 18 ms 10368 KB Output is correct
17 Correct 13 ms 6528 KB Output is correct
18 Correct 16 ms 7808 KB Output is correct
19 Correct 17 ms 9088 KB Output is correct
20 Correct 17 ms 10240 KB Output is correct
21 Correct 12 ms 6400 KB Output is correct
22 Correct 16 ms 7808 KB Output is correct
23 Correct 18 ms 9088 KB Output is correct
24 Correct 17 ms 10240 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 128056 KB Output is correct
2 Correct 1837 ms 238340 KB Output is correct
3 Correct 2408 ms 342692 KB Output is correct
4 Correct 2555 ms 451364 KB Output is correct
5 Correct 1035 ms 126620 KB Output is correct
6 Correct 1608 ms 235936 KB Output is correct
7 Correct 2295 ms 340904 KB Output is correct
8 Correct 2799 ms 445596 KB Output is correct
9 Correct 1038 ms 126108 KB Output is correct
10 Correct 1788 ms 236264 KB Output is correct
11 Correct 2283 ms 342812 KB Output is correct
12 Correct 2913 ms 447340 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5376 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct
13 Correct 12 ms 6528 KB Output is correct
14 Correct 16 ms 7808 KB Output is correct
15 Correct 18 ms 9088 KB Output is correct
16 Correct 18 ms 10368 KB Output is correct
17 Correct 13 ms 6528 KB Output is correct
18 Correct 16 ms 7808 KB Output is correct
19 Correct 17 ms 9088 KB Output is correct
20 Correct 17 ms 10240 KB Output is correct
21 Correct 12 ms 6400 KB Output is correct
22 Correct 16 ms 7808 KB Output is correct
23 Correct 18 ms 9088 KB Output is correct
24 Correct 17 ms 10240 KB Output is correct
25 Correct 1132 ms 128056 KB Output is correct
26 Correct 1837 ms 238340 KB Output is correct
27 Correct 2408 ms 342692 KB Output is correct
28 Correct 2555 ms 451364 KB Output is correct
29 Correct 1035 ms 126620 KB Output is correct
30 Correct 1608 ms 235936 KB Output is correct
31 Correct 2295 ms 340904 KB Output is correct
32 Correct 2799 ms 445596 KB Output is correct
33 Correct 1038 ms 126108 KB Output is correct
34 Correct 1788 ms 236264 KB Output is correct
35 Correct 2283 ms 342812 KB Output is correct
36 Correct 2913 ms 447340 KB Output is correct
37 Correct 1796 ms 129064 KB Output is correct
38 Correct 2482 ms 238716 KB Output is correct
39 Correct 3315 ms 347488 KB Output is correct
40 Correct 3640 ms 451980 KB Output is correct
41 Correct 2168 ms 127188 KB Output is correct
42 Correct 2965 ms 235808 KB Output is correct
43 Correct 3328 ms 341152 KB Output is correct
44 Correct 3795 ms 445116 KB Output is correct
45 Correct 1949 ms 126240 KB Output is correct
46 Correct 2773 ms 236516 KB Output is correct
47 Correct 2996 ms 341492 KB Output is correct
48 Correct 3183 ms 446964 KB Output is correct