oj.uz

Submission #308337

# Submission time Handle Problem Language Result Execution time Memory
308337 2020-10-01T00:03:20 Z ErdosSzekeres Klasika (COCI20_klasika) C++14
33 / 110
 3616 ms 499944 KB 
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pii pair<int,int>
const int MAXN = 3e5+7;
int q;
int tp[MAXN], a[MAXN], b[MAXN], d[MAXN], t=0, ent[MAXN], sai[MAXN];
int fe[8*MAXN], fd[8*MAXN], node_counter = 0;
set<int> aux[8*MAXN];//entry times
int create(){
    node_counter++;
    fe[node_counter] = -1;
    fd[node_counter] = -1;
    aux[node_counter].insert(1<<30+1);
    return node_counter;
}
vector<pii> G[MAXN];
void inserir(int idx, int depth, int val, int et){
    aux[idx].insert(et);
    if(depth < 0)return;
    if((val&(1<<depth))){//go right
        if(fd[idx] == -1)fd[idx] = create();
        inserir(fd[idx], depth-1, val, et);
    }else{
        if(fe[idx] == -1)fe[idx] = create();
        inserir(fe[idx], depth-1, val, et);
    }
}
void dfs(int u){
    t++; ent[u] = t;
    for(pii viz : G[u]){
        d[viz.first] = (d[u]^viz.second);
        dfs(viz.first);
    }
    sai[u] = t;
}
int query(int idx, int depth, int val, int node){
    if(depth < 0)return 0;
    if((val&(1<<depth))){//i want to go left
        if(fe[idx] == -1){//but i cant
            return query(fd[idx], depth-1, val, node);
        }else{
            int tst = *aux[fe[idx]].lower_bound(ent[node]);
            if(tst>=ent[node] && tst <= sai[node]){//go!!
                //cout<<tst<<" "<<ent[node]<<" "<<sai[node]<<"  --> "<<node<<endl;
                return (1<<depth) + query(fe[idx], depth-1, val, node);
            }
            return query(fd[idx], depth-1, val, node);
        }
    }else{//i want to go right
        if(fd[idx] == -1){//but i cant
            return query(fe[idx], depth-1, val, node);
        }else{
            int tst = *aux[fd[idx]].lower_bound(ent[node]);
            if(tst>=ent[node] && tst <= sai[node]){//go!!
                //cout<<tst<<" "<<ent[node]<<" "<<sai[node]<<"  --> "<<node<<endl;
                return (1<<depth) + query(fd[idx], depth-1, val, node);
            }
            return query(fe[idx], depth-1, val, node);
        }
    }
}
int main(){
    fastio; cin>>q;
    for(int i=0; i<q; i++){
        string ii; cin>>ii>>a[i]>>b[i];
        tp[i] = (ii=="Add") ? 0 : 1;
    }
    int raiz = create();
    int id = 1;
    for(int i=0; i<q; i++){//build tree and compute euler tour
        if(tp[i] == 1)continue;
        id++;
        G[a[i]].push_back({id, b[i]});
    }
    dfs(1);
    inserir(1, 30, 0, ent[1]);
    id = 1;
    for(int i=0; i<q; i++){
        if(tp[i] == 0){
            id++;
            inserir(1, 30, d[id], ent[id]);
        }else{
            cout << query(raiz, 30, d[a[i]], b[i]) << endl;//max xor with d[a[i]] in subtree of b[i]
        }
    }
}

Compilation message

klasika.cpp: In function 'int create()':
klasika.cpp:14:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |     aux[node_counter].insert(1<<30+1);
      |                                 ~~^~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 120312 KB Output is correct
2 Incorrect 82 ms 120440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 120312 KB Output is correct
2 Incorrect 82 ms 120440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 221688 KB Output is correct
2 Correct 2147 ms 315256 KB Output is correct
3 Correct 2822 ms 408564 KB Output is correct
4 Correct 3456 ms 499944 KB Output is correct
5 Correct 1495 ms 222968 KB Output is correct
6 Correct 2198 ms 315256 KB Output is correct
7 Correct 2916 ms 404088 KB Output is correct
8 Correct 3579 ms 493484 KB Output is correct
9 Correct 1515 ms 222636 KB Output is correct
10 Correct 2246 ms 315976 KB Output is correct
11 Correct 2933 ms 406304 KB Output is correct
12 Correct 3616 ms 495020 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 120312 KB Output is correct
2 Incorrect 82 ms 120440 KB Output isn't correct
3 Halted 0 ms 0 KB -