Submission #223403

#	Time	Username	Problem	Language	Result	Execution time	Memory
223403		dwsc	Klasika (COCI20_klasika)	C++14	110 / 110	3559 ms	191136 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
vector<int> adj[200005];
int start[200005],fin[200005];
int num = 0;
void dfs(int u,int pa){
    start[u] = num;
    for (int i = 0; i < adj[u].size(); i++){
        int v = adj[u][i];
        if (v == pa) continue;
        dfs(v,u);
    }
    fin[u] = num++;
}
struct node {
    node *l, *r;
    set<int> st;
    int s, m, e;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(NULL), r(NULL) {
        if (s != e) l = new node(s, m), r = new node(m+1, e);
    }
    void add(int x,int v){
       // cout << "In" << s << " " << e << "\n";
       // cout << "Adding" << x << " of weight " << v << "\n";
        st.insert(v);
        if (s != e){
            if (x <= m) l->add(x,v);
            else r->add(x,v);
        }
    }
    int query(int x,int y,int v){
        if (s == x && e == y){
            //cout <<"Calculating for"<< x << " " << y <<" "  << v << "\nSet elements";
            //for (auto it  = st.begin(); it != st.end(); ++it) cout << *it << " ";
            //cout << "\n";
            int lo = 0,hi = (1<<30)-1;
            for (int i = 29; i >= 0; i--){
                //cout << i << "th bit " << lo << " " << hi << "\n";
                if (v & (1<<i)){
                   // cout << "zero is better\n";
                    int mid = hi-(1<<i);
                    auto it = st.lower_bound(lo);
                    if (it ==st.end() || *it > mid) lo += (1<<i);
                    else hi -= (1<<i);
                }
                else{
                    //cout << "one is better\n";
                    int mid = lo+(1<<i);
                    auto it = st.lower_bound(mid);
                    if (it == st.end() || *it > hi) hi -= (1<<i);
                    else lo += (1<<i);
                }
            }
            //cout << lo << " " << hi << "done\n";
            assert(lo == hi);
            return (lo^v);
        }
        if (y <= m) return l->query(x,y,v);
        if (x > m) return r->query(x,y,v);
        return max(l->query(x,m,v),r->query(m+1,y,v));
    }
}*root;
int weight[200005];
int main(){
    int q;
    cin >> q;
    int n = 1;
    ii que[q];
    int type[q];
    for (int i = 0; i < q; i++){
        string t;
        cin >> t;
        if (t == "Add"){
            int x,w;
            cin >> x >> w;
            x--;
            adj[x].push_back(n);
            weight[n] = weight[x]^w;
            que[i] = ii(n,weight[n]);
            type[i] = 0;
            n++;
        }
        else{
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            que[i] = ii(a,b);
            type[i] = 1;
        }
    }
    root = new node(0,n-1);
    dfs(0,-1);
    root->add(fin[0],0);
    for (int i = 0; i < q; i++){
        if (type[i]){
            int a = que[i].first,b = que[i].second;
            cout << root->query(start[b],fin[b],weight[a]) << "\n";
        }
        else{
            int x = que[i].first,w = que[i].second;
            root->add(fin[x],w);
        }

    }
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:9:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                     ~~^~~~~~~~~~~~~~~
klasika.cpp: In constructor 'node::node(int, int)':
klasika.cpp:19:15: warning: 'node::e' will be initialized after [-Wreorder]
     int s, m, e;
               ^
klasika.cpp:19:12: warning:   'int node::m' [-Wreorder]
     int s, m, e;
            ^
klasika.cpp:20:5: warning:   when initialized here [-Wreorder]
     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(NULL), r(NULL) {
     ^~~~
klasika.cpp:19:12: warning: 'node::m' will be initialized after [-Wreorder]
     int s, m, e;
            ^
klasika.cpp:17:11: warning:   'node* node::l' [-Wreorder]
     node *l, *r;
           ^
klasika.cpp:20:5: warning:   when initialized here [-Wreorder]
     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(NULL), r(NULL) {
     ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44