Submission #1264594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264594		ceciver	Klasika (COCI20_klasika)	C++20	66 / 110	5089 ms	183396 KiB

klasika

/// template {{{
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <deque>
#include <chrono>
 
#ifdef LOCAL
#include "/Library/debug/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
using namespace std;
 
#define MAX                 2e9
#define MIN                 -2e9
#define by(x)				[](const auto& a, const auto& b) { return a.x < b.x; }
#define INF                 1e14
#define PI                  acos(-1.0)
#define mid(s,e)            (s+(e-s)/2)
#define clz(n)              __builtin_clzll(n)
#define nbofbits(n)         __builtin_popcountll(n)
#define all(x)              (x).begin(), (x).end()
#define endl                '\n'
#define int                 long long
#define pb                  push_back
#define sz(a)               ((int)((a).size()))
#define double              long double
#define fi					first
#define se					second
#define getunique(v)		{sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
 
//const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpdd = vector<pdd>;
// }}}

struct Trie {
    vvi nxt;
    vi childs;

    Trie() {
        nxt.push_back(vi(2,-1));
    }
    void insert(int x, bool record = true) {
        if(record) childs.pb(x);
        int curr = 0;
        for(int i=30;i>=0;i--) {
            int b = (x >> i) & 1;
            if(nxt[curr][b] == -1) {
                nxt.push_back(vi(2, -1));
                nxt[curr][b] = nxt.size() - 1;
            }
            curr = nxt[curr][b];
        }
    }

    void insert_all() {
        getunique(childs);
        nxt.clear();
        nxt.push_back(vi(2,-1));
        for(int x: childs) insert(x, false);
    }

    int mx_xor(int x) {
        if (nxt.size() == 1 && nxt[0][0] == -1 && nxt[0][1] == -1) return 0;
        int curr = 0;
        int ans = 0;
        for(int i=30;i>=0;i--) {
            int b = (x >> i) & 1;
            if(nxt[curr][!b] != -1) {
                curr = nxt[curr][!b];
                ans |= (1LL << i);
            }else {
                curr = nxt[curr][b];
            }
        }
        return ans;
    }

};



typedef Trie T;
static T unit = Trie();
struct Tree {

    T f(const T& a, const T& b) {
        if (a.childs.empty()) return b;
        if (b.childs.empty()) return a;
        T c;
        for (int x: a.childs) c.childs.pb(x);
        for (int x: b.childs) c.childs.pb(x);
        c.insert_all();
        return c;
    }
                                        //
	vector<T> s; int n;
	Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};

vvi adj;
vi path_xor;
vi in;
vi out;

void dfs(int i, int& c) {
    c++;
    in[i] = c;
    for(int u: adj[i]) {
        dfs(u, c);
    }
    out[i] = c;
}


void solve() {
    int q; cin>>q;
    vector<array<int,3>> queries(q);
    int edges = 0;

    bool flag = 1;
    for(int i=0;i<q;i++) {
        string type;
        int a, w;
        cin>>type>>a>>w;
        if(type == "Add") edges++;
        if(type == "Query") {
            flag &= w == 1;
        }
        queries[i] = {type == "Add", a - 1, w};
    }

    int n = edges + 1;

    adj = vvi(n);
    path_xor = vi(n);
    in = vi(n);
    out = vi(n);

    {
        int nxt = 1;
        for(auto [t, a, w]: queries) {
            if(t == 0) continue;
            adj[a].pb(nxt);
            path_xor[nxt] = path_xor[a] ^ w;;
            nxt++;
        }
    }

    if(flag) {
        Trie global; global.insert(0);
        int nxt = 1;
        for(auto [t, a, b]: queries) {
            if(t == 1) {
                Trie t;
                t.insert(path_xor[nxt]);
                global.insert(path_xor[nxt]);
                nxt++;
            }else {
                b--;
                if(b == 0) {
                    int ans = global.mx_xor(path_xor[a]);
                    cout<<ans<<endl;
                }
            }

        }
        return;
    }



    {
        int c = -1;
        dfs(0, c);
    }


    /*
    Tree sg(1);
    Trie t;
    t.insert(5);
    cout<<t.mx_xor(0)<<endl;
    sg.update(0, t);
    cout<<sg.query(0, 1).mx_xor(0)<<endl;
    */

    Tree sg(n);

    Trie global; global.insert(0);
    sg.update(in[0], global);

    int nxt = 1;
    for(auto [t, a, b]: queries) {
        if(t == 1) {
            Trie t;
            t.insert(path_xor[nxt]);
            sg.update(in[nxt], t);
            global.insert(path_xor[nxt]);
            nxt++;
        }else {
            b--;
            if(b == 0) {
                int ans = global.mx_xor(path_xor[a]);
                cout<<ans<<endl;
            }else {
                int ans = sg.query(in[b], out[b]+1).mx_xor(path_xor[a]);
                cout<<ans<<endl;
            }
        }
    }



}
 
void preprocessing() {
}
 
bool multi_test_cases = 0;
 
// main {{{
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);
    cout << fixed;
 
    preprocessing();
 
    int t = 1;
    if (multi_test_cases) cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
}
 
 

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