제출 #1161546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161546		asdasdqwer	Klasika (COCI20_klasika)	C++17	110 / 110	2085 ms	521068 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,2>
#define tii array<int,3>

struct Node {
    pii cld = {-1, -1};
    set<int> tm;
};

Node root;
vector<Node> trie = {root};

void insert(int val, int ndtm) {
    int idx = 0;
    trie[idx].tm.insert(ndtm);
    for (int i=30;i>=0;i--) {
        int b1 = 0;
        if (((1<<i)&val) != 0) b1 = 1;
        if (trie[idx].cld[b1] == -1) {
            Node n1;
            trie.push_back(n1);
            trie[idx].cld[b1] = (int)trie.size()-1;
        }
        idx = trie[idx].cld[b1];
        trie[idx].tm.insert(ndtm);
    }
}


const int FLL = (((int)1)<<35)-1;

int gret(int val, int start, int end) {
    int idx = 0;
    for (int i=30;i>=0;i--) {
        int b1 = 0;
        if (((1<<i)&val) != 0) b1 = 1;
        int b2 = 1 - b1;
        if (trie[idx].cld[b2] != -1) {
            auto it = trie[trie[idx].cld[b2]].tm.lower_bound(start);
            if (it != trie[trie[idx].cld[b2]].tm.end() && (*it) < end) {
                val = (val | (1<<i));
                idx = trie[idx].cld[b2];
                continue;
            }
        }
        idx = trie[idx].cld[b1];
        val = (val & (FLL ^ (1<<i)));
    }
    return val;
}

signed main() {
    int q;cin>>q;
    vector<tii> quer;
    vector<vector<int>> child(1);
    vector<int> val = {0};
    while (q--) {
        string s;cin>>s;
        if (s == "Add") {
            int x,y;cin>>x>>y;x--;
            child.push_back({});
            child[x].push_back((int)child.size()-1);
            val.push_back(y);
            quer.push_back({0, x, y});
        }

        else {
            int a,b;cin>>a>>b;
            a--;b--;
            quer.push_back({1, a, b});
        }
    }

    int n = (int)child.size();
    vector<int> tin(n, -1), tout(n, -1);
    int cnt = 0;
    vector<int> pfsm(n, 0);
    function<void(int)> dfs=[&](int node) {
        tin[node] = cnt++;
        for (auto &x:child[node]) {
            pfsm[x] = (pfsm[node] ^ val[x]);
            dfs(x);
        }

        tout[node] = cnt;
    };

    dfs(0);

    insert(0, 0);

    cnt = 1;
    for (auto &x:quer) {
        if (x[0] == 0) {
            insert(pfsm[cnt], tin[cnt]);
            cnt++;
        }

        else {
            auto [t, a, b] = x;
            int v1 = pfsm[a];
            int res = gret(v1, tin[b], tout[b]);
            cout << res << endl;
        }
    }
}

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