제출 #1312591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312591		iamsazidh	Klasika (COCI20_klasika)	C++20	110 / 110	4577 ms	304256 KiB

klasika

//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef double                 dl;
typedef vector<int>            vi;
typedef vector<vector<int>>    vii;
typedef vector<ll>             vl;
typedef vector<bool>           vb;
typedef pair<int,int>         pii;
typedef pair<ll, ll>          pll;

#define ff                first
#define ss                second
#define all(a)            a.begin(),a.end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          (a*(b/gcd(a,b)))
#define file();           freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define spc               " "

#ifdef ONLINE_JUDGE
    #define debarr(array)
    #define deb(x)
    #define del
    #define debug(...)
#else
    #define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
    #define deb(x)         cerr << #x << " = " << x << endl;
    #define del cerr << '\n';
    #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__);
    
    template <class X, class Y>
    ostream& operator<<(ostream& os, const pair<X, Y>& p) {
        return os << "(" << p.first << ", " << p.second << ")";
    }
    
    template <class Ch, class Tr, class Container>
    basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, const Container& x) {
        int i = 0, n = distance(x.begin(), x.end());
        os << "{ ";
        for (const auto& y : x)
            os << y << (++i < n ? ", " : "");
        return os << " }";
    }
    
    template <typename... Args>
    void _debug(const char* names, Args&&... args) {
        string_view s(names);
        cerr << "{ ";
        size_t i = 0, cnt = 0, n = sizeof...(args);
    
        auto next = [&]() {
            while (i < s.size() && (s[i] == ' ' || s[i] == ',')) ++i;
            size_t st = i;
            while (i < s.size() && s[i] != ',') ++i;
            return s.substr(st, i - st);
        };
    
        ((cerr << next() << ": " << args << (++cnt < n ? ", " : "")), ...);
        cerr << " }" << '\n';
    }
#endif


const double PI =         acos(-1);
const int MOD =           1000000007;
const int inf =           (2147483647);
const double EPS =        1e-6;
const int MAXN =          200000+100;
const int logN = 30;


class Trie{
    public:
    struct node{
            int child[2];
        node() {
            child[0] = child[1] = -1;
        }
    };
        set<pii> st;
        vector<node> arr;
        int timer = 1;
        Trie() {
            arr.resize(MAXN*18);
            st.insert({inf, inf});
        }
        void add(int x, int val){ // node no, value
            int now = 0;
            st.insert({now, x});
            for(int i = logN; i >= 0; i--){
                bool v = (val>>i) &1;
                if(arr[now].child[v]==-1){
                    arr[now].child[v] = timer++;
                }
                now = arr[now].child[v];
                st.insert({now, x});
            }
        }
        void remove(int x, int val){
            int now = 0;
            st.erase({now, x});
            for(int i = logN; i >= 0; i--){
                bool v = (val>>i) &1;
                now = arr[now].child[v];
                st.erase({now, x});
            }
        }
        int query(int val, int l, int r){
            int now = 0;
            int ans = 0;
            for(int i = logN; i >= 0; i--){
                bool need = !((val>>i) &1);
                int got = need;
                pii xxx = *st.lower_bound({arr[now].child[need], l});
                if(arr[now].child[need]==-1 || (xxx.ff!=arr[now].child[need]) ||  (xxx.ss>r) ) got = !need;
                if(got==need) ans += 1<<i;
                now = arr[now].child[got];
            }
            return ans;

        }
        void printAll(int k){
            int idx = 0;
            for(auto x: arr){
                if(idx>k) break;
                deb(idx++)
                // cerr << x.val << spc << x.child[0] << spc << x.child[1] << endl;
            }
        }
};

int ttimer = 0;

Trie* trie;

void dfs(vii &adj, int i, vi &xr, vector<pii> &ett){
    ett[i].ff = ++ttimer;
    trie->add(ttimer, xr[i]);
    for(auto x: adj[i]) dfs(adj, x, xr, ett);
    ett[i].ss = ttimer;
    return;
}

bool solve(){
    int q; cin >> q;
    vii adj(MAXN);
    vi xr(MAXN, 0);
    trie = new Trie();
    int timer = 2;
    
    vector<pair<int, pii>> query;
    int cntQ = 0;
    int n = 1;
    while(q--){
        string s; cin >> s;
        int x, y; cin >> x >> y;
        if(s=="Add"){
            xr[timer] = y^xr[x];
            adj[x].push_back(timer);
            query.push_back({1, {x, timer++}});
            n++;
        }else{
            query.push_back({0, {x, y}});
            cntQ++;
        }
    }
    reverse(all(query));
    vector<pii> ett(n+1);
    dfs(adj, 1, xr, ett);
    int idx = cntQ-1;
    vi ans(cntQ);
    for(auto x: query){
        if(x.ff==1){
            trie->remove(ett[x.ss.ss].ff, xr[x.ss.ss]);
        }else{
            ans[idx--] = trie->query(xr[x.ss.ff], ett[x.ss.ss].ff, ett[x.ss.ss].ss);
        }
    }
    for(auto x: ans) cout << x << endl;

    return 1;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int testcase = 1;
    //cin >> testcase;
    for(int tc = 1; tc <= testcase; tc++){
        //cerr << "TESTCASE - " << tc << endl;
        solve();
        //cout << (solve() ? "YES" : "NO") << '\n';
        cerr << endl;
    }

    return 0;
}

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