oj.uz

Submission #1110361

# Submission time Handle Problem Language Result Execution time Memory
1110361 2024-11-09T10:22:41 Z FucKanh Klasika (COCI20_klasika) C++14
11 / 110
 682 ms 524288 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23888 KB Output is correct
2 Correct 25 ms 25832 KB Output is correct
3 Correct 30 ms 31224 KB Output is correct
4 Correct 40 ms 36056 KB Output is correct
5 Correct 24 ms 22608 KB Output is correct
6 Correct 20 ms 22864 KB Output is correct
7 Correct 23 ms 23120 KB Output is correct
8 Correct 19 ms 23376 KB Output is correct
9 Correct 20 ms 22608 KB Output is correct
10 Correct 22 ms 23544 KB Output is correct
11 Correct 23 ms 24144 KB Output is correct
12 Correct 23 ms 24896 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23888 KB Output is correct
2 Correct 25 ms 25832 KB Output is correct
3 Correct 30 ms 31224 KB Output is correct
4 Correct 40 ms 36056 KB Output is correct
5 Correct 24 ms 22608 KB Output is correct
6 Correct 20 ms 22864 KB Output is correct
7 Correct 23 ms 23120 KB Output is correct
8 Correct 19 ms 23376 KB Output is correct
9 Correct 20 ms 22608 KB Output is correct
10 Correct 22 ms 23544 KB Output is correct
11 Correct 23 ms 24144 KB Output is correct
12 Correct 23 ms 24896 KB Output is correct
13 Correct 138 ms 117520 KB Output is correct
14 Correct 470 ms 374088 KB Output is correct
15 Runtime error 669 ms 524288 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 682 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23888 KB Output is correct
2 Correct 25 ms 25832 KB Output is correct
3 Correct 30 ms 31224 KB Output is correct
4 Correct 40 ms 36056 KB Output is correct
5 Correct 24 ms 22608 KB Output is correct
6 Correct 20 ms 22864 KB Output is correct
7 Correct 23 ms 23120 KB Output is correct
8 Correct 19 ms 23376 KB Output is correct
9 Correct 20 ms 22608 KB Output is correct
10 Correct 22 ms 23544 KB Output is correct
11 Correct 23 ms 24144 KB Output is correct
12 Correct 23 ms 24896 KB Output is correct
13 Correct 138 ms 117520 KB Output is correct
14 Correct 470 ms 374088 KB Output is correct
15 Runtime error 669 ms 524288 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -