Submission #1110361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110361		FucKanh	Klasika (COCI20_klasika)	C++14	11 / 110	682 ms	524288 KiB

klasika

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define p3i pair<int,pii>
#define p4i pair<pii,pii>
#define fi first
#define se second

using namespace std;

const int maxn = 2e5 + 2;

int h[maxn],ans[maxn];
vector<p3i> a[maxn];
vector<p4i> qr[maxn];

struct node {
    int u,pa,jump,len,vpa,vjump;
    node() {};
    node(int u) : u(u) {}
    node(int u, int pa, int jump, int len, int vpa,int vjump) : u(u), pa(pa), jump(jump), len(len), vpa(vpa), vjump(vjump) {}
};

node info[maxn];

void add(int u,int pa,int w) {
    h[u] = h[pa] + 1;
    int len,jump,vpa = w,vjump;
    if (info[pa].len == info[info[pa].jump].len) {
        len = info[pa].len * 2 + 1;
        jump = info[info[pa].jump].jump;
        vjump = w ^ info[pa].vjump ^ info[info[pa].jump].vjump;
    }
    else {
        len = 1;
        jump = pa;
        vjump = w;
    }
    info[u] = node(u,pa,jump,len,vpa,vjump);
}

pii binlift(int u, int k) {
    int des = h[u] - k;
    int value = 0;
    while (h[u] != des) {
//        cerr << u << " " << h[u] << " " << des << endl;
//        system("pause");
        if (h[info[u].jump] < des) {
            value ^= info[u].vpa;
            u = info[u].pa;
        }
        else {
            value ^= info[u].vjump;
            u = info[u].jump;
        }
    }
    return {u,value};
}

int LCA(int u, int v) {
    if (h[u] > h[v]) swap(u,v);
    pii tmp = binlift(v,h[v]-h[u]);
    int val = 0;
    v = tmp.first;
//    cerr << u << " " << v << endl;
    while (u != v) {
        if (info[u].jump != info[v].jump) {
            val ^= info[u].vjump ^ info[v].vjump;
            u = info[u].jump;
            v = info[v].jump;
        }
        else {
            val ^= info[u].vpa ^ info[v].vpa;
            u = info[u].pa;
            v = info[v].pa;
        }
    }
//    cerr << val << " " << tmp.second << endl;
    return val ^ tmp.second;
}

struct nodetrie {
    int la, t[2];
    nodetrie *p[2];
    nodetrie() {
        t[0] = t[1] = 0;
        p[0] = p[1] = nullptr;
        la = 0;
    }
    nodetrie(nodetrie *l, nodetrie *r, int tl, int tr) {
        t[0] = (tl);
        t[1] = (tr);
        p[0] = (l);
        p[1] = (r);
        la = 0;
    }
};

void push(nodetrie *p,int pos) {
    if (p->la) {
        for (int i = 0; i < 2; i++) {
            if (p->p[i]!=nullptr) p->p[i]->la ^= p->la;
        }
        if (p->la & (1<<pos-1)) {
            swap(p->p[0],p->p[1]), swap(p->t[0],p->t[1]);
        }
        p->la=0;
    }
}

class trie {
public:
    int sz;
    nodetrie *root = new nodetrie();
    void update(nodetrie *p, int pos, int val, int t) {
//        cerr << "update: "<< pos << endl;
        if (pos==0) return;
        push(p,pos);
        int bit = (val&(1<<pos-1))!=0;
        if (p->p[bit]==nullptr){
            p->t[bit] = t;
            p->p[bit] = new nodetrie();
        }
        else {
            p->t[bit] = min(t,p->t[bit]);
        }
        update( p->p[bit], pos - 1, val, t);
    }

    int get(nodetrie *p, int pos, int val, int t) {
        if (pos==0) return 0;
//        cerr<< pos << " " << t << endl;
        assert(p!=nullptr);
        push(p,pos);
        int bit = (val&(1<<pos-1))!=0;
//        cerr<< pos << " " << t << " " << bit << endl;
        if (p->p[bit]==nullptr || p->t[bit] > t){
//            cerr << "Ok" << endl;
            return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1);
        }
        else {
//            cerr << "xam" << endl;
            return get(p->p[bit],pos-1,val,t) | (bit << pos-1);
        }
    }

    int get(int val, int t) {
        return get(root,31,val,t);
    }

    void update(int val, int t) {
        update(root,31,val,t);
        sz++;
    }

    void addlazy(int val) {
        root->la ^= val;
    }

    void init(int t) {
//        cerr << "init: " << t << endl;
        update(root,31,0,t);
        sz = 0;
    }

    void print(nodetrie *p, int pos, int val, int t) {
//        if (pos <= 5) cerr << "> " << pos << " " << (p->la) << " | " << p->la << endl;
        push(p,pos);
        if (pos==0) {
            cerr << ">> " << val << " "<< t<< endl; return;
        }
        for (int i = 0; i < 2; i++) {
            if (p->p[i] == nullptr) continue;
            print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i]));
        }
    }
    void print(int u) {
        cerr << "tree print: " << u << endl;
        print(root,31,0,0);
    }
};

void merged(nodetrie *a, nodetrie *b, int pos) {
    if (pos==0) return;
    push(a,pos);
    push(b,pos);
//    cerr << "merge: " << pos << endl;
    for (int i = 0; i < 2; i++) {
        if (b->p[i] == nullptr) continue;
        if (a->p[i] == nullptr) {
            a->p[i] = new nodetrie();
            a->t[i] = b->t[i];
        }
        else {
            a->t[i] = min(a->t[i], b->t[i]);
        }
        merged(a->p[i], b->p[i], pos - 1);
    }
}

trie tree[maxn];

void dfs(int u) {
//    cerr <<"vst u:" << u << endl;
    if (a[u].empty()) {
//        tree[u].print(u);
        for (p4i val : qr[u]) {
            int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se;
            int ori = LCA(x,y);
//            cerr << "ori: " << ori << endl;
            ans[idx] = ori ^ tree[u].get(~ori,t);
        }
        return;
    }
    for (p3i tmp : a[u]) {
        int w,v;
        w = tmp.se.fi;
        v = tmp.fi;
        tree[v].init(tmp.se.se);
        dfs(v);
        tree[v].addlazy(w);
        if (tree[u].sz < tree[v].sz) swap(tree[u], tree[v]);
        merged(tree[u].root, tree[v].root, 31);
    }
//    tree[u].print(u);
    for (p4i val : qr[u]) {
        int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se;
        int ori = LCA(x,y);
//        cerr << ori << " : " << t << endl;
        ans[idx] = ori ^ tree[u].get(~ori,t);
    }
}

void solve() {
    int q; cin >> q;
    int cnt = 1, cntqr=0, t = 0;
    info[1] = node(1,0,0,-1,0,0);
    for (int i = 1; i <= q; i++) {
        string s;cin >> s;
        t++;
        if (s=="Add") {
            int x,w; cin >> x >> w;
            add(++cnt,x,w);
            a[x].push_back({cnt,{w,t}});
        }
        else {
            int x,y; cin >> x >> y;
            qr[y].push_back({{x,y},{++cntqr,t}});
        }
    }
    tree[1].init(0);
    dfs(1);
    for (int i = 1; i <= cntqr; i++) {
        cout << ans[i] << '\n';
    }
}
void file(string name) {
    if (fopen((name + ".inp").c_str(), "r")) {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
signed main() {
    file("TaskKlasika");
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void push(nodetrie*, int)':
klasika.cpp:104:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  104 |         if (p->la & (1<<pos-1)) {
      |                         ~~~^~
klasika.cpp: In member function 'void trie::update(nodetrie*, int, int, int)':
klasika.cpp:119:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  119 |         int bit = (val&(1<<pos-1))!=0;
      |                            ~~~^~
klasika.cpp: In member function 'int trie::get(nodetrie*, int, int, int)':
klasika.cpp:135:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  135 |         int bit = (val&(1<<pos-1))!=0;
      |                            ~~~^~
klasika.cpp:139:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  139 |             return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1);
      |                                                           ~~~^~
klasika.cpp:143:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  143 |             return get(p->p[bit],pos-1,val,t) | (bit << pos-1);
      |                                                         ~~~^~
klasika.cpp: In member function 'void trie::print(nodetrie*, int, int, int)':
klasika.cpp:174:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  174 |             print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i]));
      |                                             ~~~^~
klasika.cpp: In function 'void file(std::string)':
klasika.cpp:259:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  259 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:260:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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