二维 vector MLE
查看原帖
二维 vector MLE
184198
Kanoon楼主2024/1/3 17:02

字典树使用二维 vector 的话 C++17 会 MLE,二维 int 数组或 vector<array<int, 2>> 都没问题,想问下可以用二维 vector 的方式过吗

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 10;

vector nxt(N << 5, vector<int>(2));

struct Trie {
	// int nxt[N << 5][2];
	int cnt = 0;

	void insert(int x) {
		int p = 0;
		for (int i = 30; i >= 0; i--) {
			int c = (x >> i) & 1;
			if (nxt[p][c] == 0) {
				nxt[p][c] = ++cnt;
			}
			p = nxt[p][c];
		}
	}

	int get(int x) {
		int p = 0, res = 0;
		for (int i = 30; i >= 0; i--) {
			int c = (x >> i) & 1;
			if (nxt[p][c ^ 1]) {
				p = nxt[p][c ^ 1];
				res |= 1 << i;
			} else {
				p = nxt[p][c];
			}
		}
		return res;
	}
} T;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<vector<pair<int, int>>> G(n);
	for (int i = 0; i < n - 1; i++) {
	    int u, v, w;
	    cin >> u >> v >> w;
	    --u, --v;
	    G[u].emplace_back(v, w);
	    G[v].emplace_back(u, w);
	}

	int ans = 0;

	vector<int> xor_sum(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		T.insert(xor_sum[u]);
		ans = max(ans, T.get(xor_sum[u]));
		for (auto [v, w] : G[u]) {
			if (v == p) {
				continue;
			}
			xor_sum[v] = xor_sum[u] ^ w;
			dfs(v, u);
		}
	};
	dfs(0, -1);

	cout << ans << "\n";

	return 0;
}
2024/1/3 17:02
加载中...