oj.uz

Submission #1033811

# Submission time Handle Problem Language Result Execution time Memory
1033811 2024-07-25T06:41:13 Z doducanh Klasika (COCI20_klasika) C++14
110 / 110
 1811 ms 439380 KB 
///breaker
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ii pair<int,int>
#define bit(x,i) ((x>>i)&1)
struct queries
{
    bool type;
    int u,v;
};
const int maxn=2e5+3;
int n;
queries e[maxn];
vector<ii>adj[maxn];
struct node{
    set<int>se;
    node *one,*zero;
    node(){
        zero=one=NULL;
    }
}root;
void add(node *curr,int i,int x,int &pos){
    curr->se.insert(pos);
    if(i<0)return;
    if(!bit(x,i)){
        if(curr->zero==NULL)curr->zero=new node();
        add(curr->zero,i-1,x,pos);
    }
    else{
        if(curr->one==NULL)curr->one=new node();
        add(curr->one,i-1,x,pos);
    }
}
int get(node *curr,int i,int &val,int &l,int &r){
    if(i<0)return 0;
    if(bit(val,i)==0){
        if(curr->one==NULL||(curr->one->se.lower_bound(l)==curr->one->se.upper_bound(r)))return get(curr->zero,i-1,val,l,r);
        else return ((1<<i)+get(curr->one,i-1,val,l,r));
    }
    else{
        if(curr->zero==NULL||(curr->zero->se.lower_bound(l)==curr->zero->se.upper_bound(r)))return get(curr->one,i-1,val,l,r);
        else return ((1<<i)+get(curr->zero,i-1,val,l,r));
    }
}
int cnt=0;
int d[maxn];
int in[maxn],out[maxn];
void dfs(int u,int par)
{
    in[u]=++cnt;
    for(ii a:adj[u]){
        int v=a.fi;
        int w=a.se;
        d[v]=d[u]^w;
        dfs(v,u);
    }
    out[u]=cnt;
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1,j=2;i<=n;i++){
        string s;
        cin>>s;
        cin>>e[i].u>>e[i].v;
        if(s[0]=='A'){
            e[i].type=false;
            adj[e[i].u].push_back({j,e[i].v});
            j++;
        }
        else e[i].type=true;
    }
    d[1]=0;
    dfs(1,0);
    add(&root,30,0,in[1]);
    for(int i=1,j=2;i<=n;i++){
        if(e[i].type==0){
            add(&root,30,d[j],in[j]);
            j++;
        }
        else{
            cout<<get(&root,30,d[e[i].u],in[e[i].v],out[e[i].v])<<"\n";
        }
    }
    return 0;
}

Compilation message

klasika.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main(){
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 2 ms 5580 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 2 ms 5256 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5208 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 2 ms 5580 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 2 ms 5256 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5208 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 5 ms 6488 KB Output is correct
14 Correct 5 ms 7772 KB Output is correct
15 Correct 6 ms 9052 KB Output is correct
16 Correct 8 ms 10332 KB Output is correct
17 Correct 5 ms 6492 KB Output is correct
18 Correct 6 ms 7772 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct
20 Correct 8 ms 10076 KB Output is correct
21 Correct 5 ms 6484 KB Output is correct
22 Correct 6 ms 7772 KB Output is correct
23 Correct 8 ms 9052 KB Output is correct
24 Correct 8 ms 10076 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 124752 KB Output is correct
2 Correct 863 ms 232020 KB Output is correct
3 Correct 1267 ms 335156 KB Output is correct
4 Correct 1366 ms 438732 KB Output is correct
5 Correct 559 ms 122452 KB Output is correct
6 Correct 963 ms 227924 KB Output is correct
7 Correct 1466 ms 328920 KB Output is correct
8 Correct 1658 ms 429904 KB Output is correct
9 Correct 536 ms 122196 KB Output is correct
10 Correct 816 ms 228832 KB Output is correct
11 Correct 1087 ms 331348 KB Output is correct
12 Correct 1348 ms 432280 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 2 ms 5580 KB Output is correct
5 Correct 3 ms 5156 KB Output is correct
6 Correct 2 ms 5256 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5208 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 5 ms 6488 KB Output is correct
14 Correct 5 ms 7772 KB Output is correct
15 Correct 6 ms 9052 KB Output is correct
16 Correct 8 ms 10332 KB Output is correct
17 Correct 5 ms 6492 KB Output is correct
18 Correct 6 ms 7772 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct
20 Correct 8 ms 10076 KB Output is correct
21 Correct 5 ms 6484 KB Output is correct
22 Correct 6 ms 7772 KB Output is correct
23 Correct 8 ms 9052 KB Output is correct
24 Correct 8 ms 10076 KB Output is correct
25 Correct 630 ms 124752 KB Output is correct
26 Correct 863 ms 232020 KB Output is correct
27 Correct 1267 ms 335156 KB Output is correct
28 Correct 1366 ms 438732 KB Output is correct
29 Correct 559 ms 122452 KB Output is correct
30 Correct 963 ms 227924 KB Output is correct
31 Correct 1466 ms 328920 KB Output is correct
32 Correct 1658 ms 429904 KB Output is correct
33 Correct 536 ms 122196 KB Output is correct
34 Correct 816 ms 228832 KB Output is correct
35 Correct 1087 ms 331348 KB Output is correct
36 Correct 1348 ms 432280 KB Output is correct
37 Correct 828 ms 125732 KB Output is correct
38 Correct 1159 ms 232200 KB Output is correct
39 Correct 1464 ms 338000 KB Output is correct
40 Correct 1547 ms 439380 KB Output is correct
41 Correct 943 ms 123120 KB Output is correct
42 Correct 1321 ms 227880 KB Output is correct
43 Correct 1802 ms 329184 KB Output is correct
44 Correct 1811 ms 429288 KB Output is correct
45 Correct 955 ms 122760 KB Output is correct
46 Correct 1311 ms 228940 KB Output is correct
47 Correct 1555 ms 329972 KB Output is correct
48 Correct 1698 ms 432180 KB Output is correct