Submission #416683

#	Time	Username	Problem	Language	Result	Execution time	Memory
416683		fvogel499	Klasika (COCI20_klasika)	C++14	110 / 110	3564 ms	524288 KiB

klasika

/*
File created on 06/02/2021 at 18:42:44.
Link to problem: https://oj.uz/problem/view/COCI20_klasika
Description: use a trie structure, and to only consider subtree nodes use a disc/finish array;
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define mp pair<pii, int>
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert
#define cls clear

#define ll long long

const int siz = 2e5;
const int MAX_P2 = 30;

vector<int> graph [siz];
int par [siz];
int xorTill [siz];
int disc [siz];
int rightMost [siz];

int tim = 0;
int dfs(int cn) {
    disc[cn] = tim;
    rightMost[cn] = tim;
    tim++;
    for (int nn : graph[cn]) rightMost[cn] = dfs(nn);
    return rightMost[cn];
}

struct Node {
    Node() {
        lft = nullptr;
        rgt = nullptr;
    }
    void add(int v, int k, int tins) {
        if (k == MAX_P2) return;
        int i = (v>>(MAX_P2-1-k))%2;
        if (i == 0) {
            if (lft == nullptr) lft = new Node();
            zero.ins(tins);
            lft->add(v, k+1, tins);
        }
        else {
            if (rgt == nullptr) rgt = new Node();
            one.ins(tins);
            rgt->add(v, k+1, tins);
        }
    }
    int get(int v, int k, int lb, int rb) {
        if (k == MAX_P2) return 0;
        //
        int i = (v>>(MAX_P2-1-k))%2;
        //
        auto it1 = zero.upper_bound(lb-1);
        bool lftFind = (it1 != zero.end() and (*it1) <= rb);
        //
        auto it2 = one.upper_bound(lb-1);
        bool rgtFind = (it2 != one.end() and (*it2) <= rb);
        //
        if ((i == 0 and !rgtFind) or (i == 1 and lftFind)) {
            return lft->get(v, k+1, lb, rb);
        }
        else {
            return (1<<(MAX_P2-1-k))+rgt->get(v, k+1, lb, rb);
        }
    }
    set<int> zero, one;
    Node* lft, * rgt;
};

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int q;
    cin >> q;
    par[0] = -1;

    xorTill[0] = 0;
    int n = 1;
    vector<pii> queries;
    for (int i = 0; i < q; i++) {
        string typ;
        cin >> typ;
        if (typ == "Add") {
            int parentNode, edgeWeight;
            cin >> parentNode >> edgeWeight;
            // bitset<MAX_P2> bit(edgeWeight);
            // bitset<MAX_P2> newBit;
            // for (int i = 0; i < MAX_P2; i++) newBit[i] = bit[MAX_P2-i-1];
            // edgeWeight = newBit.to_ulong();
            parentNode--;
            int curNode = n;
            graph[parentNode].pb(curNode);
            par[curNode] = parentNode;
            xorTill[curNode] = xorTill[parentNode]^edgeWeight;
            queries.pb(pii(curNode, -1));
            n++;
        }
        else {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            queries.pb(pii(a, b));
        }
    }

    dfs(0);

    Node* root = new Node();
    root->add(0, 0, disc[0]);
    for (pii i : queries) {
        if (i.s == -1) {
            root->add(xorTill[i.f], 0, disc[i.f]);
        }
        else {
            int aNode = i.f;
            int bNode = i.s;
            int xorDefault = xorTill[aNode];
            int xorMax = root->get(xorDefault, 0, disc[bNode], rightMost[bNode]);
            cout << (xorDefault^xorMax) << endl;
        }
    }

    int d = 0;
    d++;
}

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