제출 #1173145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173145		rayan_bd	Klasika (COCI20_klasika)	C++17	0 / 110	681 ms	589824 KiB

klasika

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

#define getar(ar,n) for(int i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define nl '\n'

const int mxN = 2e5 + 500;

int N=1, idx=0, parent[mxN], depth[mxN], heavy[mxN], head[mxN], sz[mxN], tin[mxN], tout[mxN], seg[mxN*4], val[mxN], till[mxN];
vector<pair<int,int>> adj[mxN];

struct Node {
    Node* children[2];
    Node() {
        children[0] = children[1] = nullptr;
    }
};

struct Trie {
    Node* root;
    Trie() { root = new Node(); }

    void add(int x) {
        Node* curr = root;
        for (int i = 30; i >= 0; --i) {
            int bit = (x >> i) & 1;
            if (!curr->children[bit]) {
                curr->children[bit] = new Node();
            }
            curr = curr->children[bit];
        }
    }

    int qry(int x) {
        Node* curr = root;
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            int bit = (x >> i) & 1;
            if (curr->children[1 - bit]) {
                curr = curr->children[1 - bit];
                ans |= (1 << i);
            } else {
                curr = curr->children[bit];
            }
        }
        return ans;
    }
};

unordered_map<int, Trie> t;

struct SegTree {
    void update_1(int node, int start, int end, int idx, int val) {
        if (start == end) {
            seg[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update_1(2 * node + 1, start, mid, idx, val);
        else update_1(2 * node + 2, mid + 1, end, idx, val);
        seg[node] = seg[2 * node + 1] ^ seg[2 * node + 2];
    }

    void update_2(int node, int start, int end, int idx, int val) {
        if (!t.count(node)) t[node] = Trie();
        t[node].add(val);
        if (start == end) return;
        int mid = (start + end) / 2;
        if (idx <= mid) update_2(2 * node + 1, start, mid, idx, val);
        else update_2(2 * node + 2, mid + 1, end, idx, val);
    }

    int qry_answer(int node, int start, int end, int l, int r, int val) {
        if (start > r || end < l) return 0;
        if (start >= l && end <= r) return t[node].qry(val);
        int mid = (start + end) / 2;
        return max(qry_answer(2 * node + 1, start, mid, l, r, val), qry_answer(2 * node + 2, mid + 1, end, l, r, val));
    }

    int xor_qry(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        if (start >= l && end <= r) return seg[node];
        int mid = (start + end) / 2;
        return xor_qry(2 * node + 1, start, mid, l, r) ^ xor_qry(2 * node + 2, mid + 1, end, l, r);
    }
} seg_tree;

struct HLD {
    void dfs(int u = 1, int par = 0) {
        sz[u] = 1;
        parent[u] = par;
        depth[u] = depth[par] + 1;
        for (auto it : adj[u]) {
            if (it.first != par) {
                val[it.first] = it.second;
                dfs(it.first, u);
                sz[u] += sz[it.first];
                if (sz[heavy[u]] < sz[it.first]) heavy[u] = it.first;
            }
        }
    }

    void dfsHLD(int u = 1, int chain = 1) {
        head[u] = chain;
        tin[u] = idx++;
        seg_tree.update_1(0, 0, N - 1, tin[u], val[u]);
        if (heavy[u]) dfsHLD(heavy[u], chain);
        for (auto it : adj[u]) {
            if (it.first != parent[u] && it.first != heavy[u]) {
                dfsHLD(it.first, it.first);
            }
        }
        tout[u] = idx - 1;
    }

    int path_xor(int u, int v) {
        int ans = 0;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) swap(u, v);
            ans ^= seg_tree.xor_qry(0, 0, N - 1, tin[head[u]], tin[u]);
            u = parent[head[u]];
        }
        if (depth[u] < depth[v]) swap(u, v);
        return (ans ^ seg_tree.xor_qry(0, 0, N - 1, tin[v], tin[u])) ^ val[v];
    }
} hld;

void lets_go() {
    int q, u, v;
    cin >> q;
    string type;
    vector<vector<int>> Q;
    for (int i = 0; i < q; ++i) {
        cin >> type >> u >> v;
        if (type == "Add") {
            Q.pb({1, u, ++N, v});
            adj[u].pb({N, v});
        } else {
            Q.pb({0, u, v});
        }
    }

    hld.dfs();
    hld.dfsHLD();
    t[0].add(0);

    for (auto it : Q) {
        if (it[0] == 1) {
            till[it[2]] = till[it[1]] ^ it[3];
            seg_tree.update_2(0, 0, N - 1, tin[it[2]], till[it[2]]);
        } else {
            u = it[1], v = it[2];
            show(seg_tree.qry_answer(0, 0, N - 1, tin[v], tout[v], hld.path_xor(u, v) ^ till[v]));
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    lets_go();
    return 0;
}

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