제출 #1264608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264608		ceciver	Klasika (COCI20_klasika)	C++20	66 / 110	993 ms	589824 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 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 {
    vector<array<int32_t,2>> nxt;
    Trie() { 
        nxt.push_back({-1,-1});
    }

    inline void insert(uint32_t x) {
        if(nxt.empty()) {
            nxt.push_back({-1,-1});
        }
        int u = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (x >> i) & 1;
            int v = nxt[u][b];
            if (v == -1) {
                v = (int)nxt.size();
                nxt[u][b] = v;
                nxt.push_back({-1,-1});
            }
            u = v;
        }
    }
    inline int mx_xor(uint32_t x) const {
        if(nxt.empty()) return 0;
        if (nxt.size()==1 && nxt[0][0]==-1 && nxt[0][1]==-1) return 0;
        int u = 0, ans = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (x >> i) & 1, want = b ^ 1;
            int go = nxt[u][want];
            if (go != -1) { ans |= (1<<i); u = go; }
            else {
                go = nxt[u][b];
                if (go == -1) break;
                u = go;
            }
        }
        return ans;
    }
};

struct Tree {
    int n;
    vector<Trie> s;

    Tree(int n=0): n(n), s(2*n) {}

    inline void point_add(int pos, uint32_t val) {
        for (pos += n; pos; pos >>= 1) s[pos].insert(val);
    }

    inline int query_max_xor(int l, int r, uint32_t x) const {
        int ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = max(ans, s[l++].mx_xor(x));
            if (r & 1) ans = max(ans, s[--r].mx_xor(x));
        }
        return ans;
    }
};



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;
    */

    adj.clear();

    Tree sg(n);

    {
    }

    int nxt = 1;
    for(auto [t, a, b]: queries) {
        if(t == 1) {
            sg.point_add(in[nxt], path_xor[nxt]);
            nxt++;
        }else {
            b--;
            int ans = sg.query_max_xor(in[b], out[b]+1, path_xor[a]);
            if(b == 0) ans = max(ans, 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