제출 #1129240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129240		VMaksimoski008	Klasika (COCI20_klasika)	C++17	110 / 110	2001 ms	435472 KiB

klasika

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 5;

struct node {
    node* mp[2];
    set<int> st;
    node() { mp[0] = mp[1] = nullptr; }
};

struct trie {
    node *root;
    trie() { root = new node(); }

    void insert(int x, int t) {
        node *u = root;
        u->st.insert(t);
        // cout << "i " << x << " " << t << '\n';
        for(int i=30; i>=0; i--) {
            bool b = x & (1 << i);
            if(u->mp[b] == nullptr) u->mp[b] = new node();
            u = u->mp[b];
            u->st.insert(t);
        }
    }

    int query(int x, int in, int out) {
        int ans = 0;
        node *u = root;
        // cout << "q " << x << " " << in << " " << out << '\n';
        for(int i=30; i>=0; i--) {
            bool b = x & (1 << i), ok = 0;
            if(u->mp[!b]) {
                auto it = u->mp[!b]->st.lower_bound(in);
                if(i == 2) {
                    // cout << (!b) << ": ";
                    // for(auto el : u->mp[!b]->st) cout << el << " ";
                    // cout << endl;
                }
                // if(it != u->mp[!b]->st.end()) cout << i << " " << *it << '\n';
                if(it != u->mp[!b]->st.end() && *it <= out) {
                    ans ^= (1 << i);
                    u = u->mp[!b];
                    ok = 1;
                    // cout << i << " good\n";
                }
            }

            if(!ok && u->mp[b]) {
                auto it = u->mp[b]->st.lower_bound(in);
                if(it != u->mp[b]->st.end() && *it <= out) {
                    u = u->mp[b];
                    ok = 1;
                    // cout << i << " bad\n";
                }
            }

            if(!ok) break;
        }

        return ans;
    }
};

int n=1, q, a[maxn], in[maxn], out[maxn], timer = 0;
vector<int> G[maxn];

void dfs(int u) {
    in[u] = timer++;
    for(int v : G[u]) a[v] ^= a[u], dfs(v);
    out[u] = timer - 1;
}

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

    cin >> q;
    vector<ar<int, 3> > qus(q+1);

    for(int i=1; i<=q; i++) {
        string s; cin >> s >> qus[i][1] >> qus[i][2];
        qus[i][0] = (s[0] == 'A');
        if(qus[i][0]) {
            G[qus[i][1]].push_back(++n);
            a[n] = qus[i][2];
        }
    }

    dfs(1);
    // for(int i=1; i<=n; i++) cout << in[i] << " ";
    // cout << '\n';
    trie trie; trie.insert(0, 0);
    n = 1;
    for(int i=1; i<=q; i++) {
        if(qus[i][0] == 1) { n++; trie.insert(a[n], in[n]); }
        else cout << trie.query(a[qus[i][1]], in[qus[i][2]], out[qus[i][2]]) << '\n';
    }

    return 0;
}

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