oj.uz

Submission #211217

# Submission time Handle Problem Language Result Execution time Memory
211217 2020-03-19T13:31:04 Z sm1ley Klasika (COCI20_klasika) C++17
33 / 110
 2490 ms 524288 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=31;i>=-1;i--){
        t->times.insert(num);
        if(t->bit[1]==NULL)t->bit[1]=new Node();
        if(t->bit[0]==NULL)t->bit[0]=new Node();
        if(val&(1<<i)){
            t = t->bit[1];
        }else{
            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=31;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 5504 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 8 ms 5888 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5632 KB Output is correct
8 Correct 8 ms 5888 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 9 ms 5632 KB Output is correct
11 Correct 8 ms 5760 KB Output is correct
12 Correct 9 ms 5888 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 5504 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 8 ms 5888 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5632 KB Output is correct
8 Correct 8 ms 5888 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 9 ms 5632 KB Output is correct
11 Correct 8 ms 5760 KB Output is correct
12 Correct 9 ms 5888 KB Output is correct
13 Correct 13 ms 7296 KB Output is correct
14 Correct 16 ms 9216 KB Output is correct
15 Correct 18 ms 11136 KB Output is correct
16 Correct 20 ms 12928 KB Output is correct
17 Correct 14 ms 7168 KB Output is correct
18 Correct 16 ms 9216 KB Output is correct
19 Correct 18 ms 11008 KB Output is correct
20 Correct 19 ms 12800 KB Output is correct
21 Correct 14 ms 7168 KB Output is correct
22 Correct 16 ms 9088 KB Output is correct
23 Correct 18 ms 11000 KB Output is correct
24 Correct 20 ms 12800 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 176144 KB Output is correct
2 Correct 1916 ms 328736 KB Output is correct
3 Correct 2490 ms 474260 KB Output is correct
4 Runtime error 2363 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 8 ms 5888 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5632 KB Output is correct
8 Correct 8 ms 5888 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 9 ms 5632 KB Output is correct
11 Correct 8 ms 5760 KB Output is correct
12 Correct 9 ms 5888 KB Output is correct
13 Correct 13 ms 7296 KB Output is correct
14 Correct 16 ms 9216 KB Output is correct
15 Correct 18 ms 11136 KB Output is correct
16 Correct 20 ms 12928 KB Output is correct
17 Correct 14 ms 7168 KB Output is correct
18 Correct 16 ms 9216 KB Output is correct
19 Correct 18 ms 11008 KB Output is correct
20 Correct 19 ms 12800 KB Output is correct
21 Correct 14 ms 7168 KB Output is correct
22 Correct 16 ms 9088 KB Output is correct
23 Correct 18 ms 11000 KB Output is correct
24 Correct 20 ms 12800 KB Output is correct
25 Correct 1407 ms 176144 KB Output is correct
26 Correct 1916 ms 328736 KB Output is correct
27 Correct 2490 ms 474260 KB Output is correct
28 Runtime error 2363 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -