結果

問題 No.1769 Don't Stop the Game
ユーザー polylogKpolylogK
提出日時 2021-10-29 20:23:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,937 bytes
コンパイル時間 1,973 ms
コンパイル使用メモリ 103,732 KB
実行使用メモリ 43,032 KB
最終ジャッジ日時 2023-09-12 04:53:23
合計ジャッジ時間 33,502 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
43,032 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 145 ms
17,700 KB
testcase_26 AC 442 ms
36,380 KB
testcase_27 WA -
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #include <testlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

#define NDEBUG

using i64 = long long;

bool deleted[200'000];
int size[200'000];

struct solve_t {
	std::vector<std::vector<int>> g;
	std::vector<int> a, b, c;

	solve_t(int n): g(n) {}
	void add_edge(int u, int v, int w) {
		g[u].push_back(a.size());
		g[v].push_back(a.size());
		a.push_back(u);
		b.push_back(v);
		c.push_back(w);
	}

	i64 solve(int start = 0) {
		i64 answer = (i64)g.size() * ((i64)g.size() - 1);

		auto solve = [&](auto&& solve, int root) -> void {
			auto calc_size = [&](auto&& dfs, int v, int par) -> int {
				size[v] = 1;
				for(int id: g[v]) {
					int to = v ^ a[id] ^ b[id];
					if(to == par or deleted[to]) continue;

					size[v] += dfs(dfs, to, v);
				}
				return size[v];
			}; calc_size(calc_size, root, -1);

			auto get_centroid = [&](auto&& dfs, int v, int par) -> int {
				for(int id: g[v]) {
					int to = v ^ a[id] ^ b[id];
					if(to == par or deleted[to]) continue;

					if(size[to] * 2 > size[root]) return dfs(dfs, to, v);
				}
				return v;
			};
			int centroid = get_centroid(get_centroid, root, -1);
			deleted[centroid] = true;

			#ifndef NDEBUG
			printf("root: %d\n", root + 1);
			printf("centroid: %d\n", centroid + 1);
			for(auto e: deleted) printf("%d ", (int)e); puts("");
			for(auto e: size) printf("%d ", e); puts("");
			for(int id: g[centroid]) if(!deleted[a[id] ^ b[id] ^ centroid])
				printf("%d ", (a[id] ^ b[id] ^ centroid) + 1); puts("");
			#endif

			calc_size(calc_size, centroid, -1);
			{ // unroll-looping
				std::map<int, int> map;
				for(int i = 0; i < g[centroid].size(); i++) {
					int id = g[centroid][i];
					int to = centroid ^ a[id] ^ b[id];
					if(deleted[to]) continue;

					{ // counting 0-xor paths
						std::set<int> xor_path; xor_path.insert(0);
						auto dfs = [&](auto&& dfs, int v, int par, int xor_val) -> void {
							bool append = false;
							if(!xor_path.count(xor_val)) {
								answer -= map[xor_val];

								xor_path.insert(xor_val);
								append = true;
							}

							for(int id: g[v]) {
								int to = v ^ a[id] ^ b[id];
								if(to == par or deleted[to]) continue;

								dfs(dfs, to, v, xor_val ^ c[id]);
							};

							if(append) {
								xor_path.erase(xor_val);
							}
						}; dfs(dfs, to, centroid, c[id]);
					}
					{ // mapping path xors
						std::set<int> xor_path;
						auto dfs = [&](auto&& dfs, int v, int par, int xor_val) -> void {
							bool append = false;
							if(!xor_path.count(xor_val)) {
								map[xor_val] += size[v];

								xor_path.insert(xor_val);
								append = true;
							}

							for(int id: g[v]) {
								int to = v ^ a[id] ^ b[id];
								if(to == par or deleted[to]) continue;

								dfs(dfs, to, v, xor_val ^ c[id]);
							};

							if(append) {
								xor_path.erase(xor_val);
							}
						}; dfs(dfs, to, centroid, c[id]);
					}
				}
				{ // unroll-looping
					std::map<int, int> map;
					for(int i = (int)g[centroid].size() - 1; i >= 0; i--) {
						int id = g[centroid][i];
						int to = centroid ^ a[id] ^ b[id];
						if(deleted[to]) continue;

						solve(solve, to);

						{ // counting 0-xor paths
							std::set<int> xor_path; xor_path.insert(0);
							auto dfs = [&](auto&& dfs, int v, int par, int xor_val) -> void {
								if(xor_path.count(xor_val)) { // [u-centroid]
									answer -= size[centroid] - size[to];
								}

								bool append = false;
								if(!xor_path.count(xor_val)) {
									answer -= map[xor_val];

									xor_path.insert(xor_val);
									append = true;
								}

								for(int id: g[v]) {
									int to = v ^ a[id] ^ b[id];
									if(to == par or deleted[to]) continue;

									dfs(dfs, to, v, xor_val ^ c[id]);
								};

								if(append) {
									xor_path.erase(xor_val);
								}
							}; dfs(dfs, to, centroid, c[id]);
						}
						{ // mapping path xors
							std::set<int> xor_path;
							auto dfs = [&](auto&& dfs, int v, int par, int xor_val) -> void {
								bool append = false;
								if(!xor_path.count(xor_val)) {
									map[xor_val] += size[v];

									xor_path.insert(xor_val);
									append = true;
								}

								for(int id: g[v]) {
									int to = v ^ a[id] ^ b[id];
									if(to == par or deleted[to]) continue;

									dfs(dfs, to, v, xor_val ^ c[id]);
								};

								if(append) {
									xor_path.erase(xor_val);
								}
							}; dfs(dfs, to, centroid, c[id]);
						}
					}

					answer -= map[0];
				}
			}

			deleted[centroid] = false;
		}; solve(solve, start);

		return answer;
	}
};

int main() {
	int n; scanf("%d", &n);

	solve_t solver(n);
	for(int i = 0; i < n - 1; i++) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);

		solver.add_edge(u - 1, v - 1, w);
	}
	printf("%lld\n", solver.solve());
}
0