結果

問題 No.1769 Don't Stop the Game
ユーザー 👑 ygussanyygussany
提出日時 2021-11-13 14:32:57
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 210 ms / 3,000 ms
コード長 2,915 bytes
コンパイル時間 1,042 ms
コンパイル使用メモリ 31,988 KB
実行使用メモリ 46,604 KB
最終ジャッジ日時 2023-09-12 05:02:16
合計ジャッジ時間 5,580 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
21,868 KB
testcase_01 AC 6 ms
22,784 KB
testcase_02 AC 6 ms
22,940 KB
testcase_03 AC 7 ms
22,848 KB
testcase_04 AC 7 ms
24,492 KB
testcase_05 AC 6 ms
22,788 KB
testcase_06 AC 7 ms
21,584 KB
testcase_07 AC 7 ms
21,960 KB
testcase_08 AC 107 ms
30,948 KB
testcase_09 AC 77 ms
26,956 KB
testcase_10 AC 137 ms
31,044 KB
testcase_11 AC 78 ms
28,940 KB
testcase_12 AC 138 ms
31,044 KB
testcase_13 AC 135 ms
30,920 KB
testcase_14 AC 132 ms
31,096 KB
testcase_15 AC 144 ms
30,984 KB
testcase_16 AC 148 ms
33,076 KB
testcase_17 AC 157 ms
31,024 KB
testcase_18 AC 167 ms
33,156 KB
testcase_19 AC 190 ms
31,040 KB
testcase_20 AC 206 ms
31,032 KB
testcase_21 AC 210 ms
31,060 KB
testcase_22 AC 203 ms
31,112 KB
testcase_23 AC 135 ms
29,060 KB
testcase_24 AC 140 ms
31,100 KB
testcase_25 AC 60 ms
28,880 KB
testcase_26 AC 88 ms
30,984 KB
testcase_27 AC 97 ms
44,624 KB
testcase_28 AC 116 ms
46,604 KB
testcase_29 AC 109 ms
38,940 KB
testcase_30 AC 104 ms
38,856 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <stdio.h>

typedef struct Edge {
	struct Edge *next;
	int v, cost;
} edge;

#define HASH 1000003
const int H_Mod = HASH;

typedef struct List {
	struct List *next;
	int v, cur;
} list;

void DFS(edge* adj[], int u, int par[], int val[], list* hash[])
{
	int h = val[u] % H_Mod, w;
	edge *p;
	list *hp;
	for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
	par[u] = hp->cur;
	for (p = adj[u]; p != NULL; p = p->next) {
		w = p->v;
		hp->cur = w;
		if (par[w] < 0) DFS(adj, w, par, val, hash);
		hp->cur = par[u];
	}
}

int main()
{
	int i, N, u, w, c;
	edge *adj[200001] = {}, e[400001], *p;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d %d", &u, &w, &c);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].cost = c;
		e[i*2+1].cost = c;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int h, par[200001] = {}, val[200001], q[200001], head, tail;
	list *hash[HASH] = {}, hd[200001], *hp;
	par[1] = 1;
	val[1] = 0;
	q[0] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		u = q[head];
		h = val[u] % H_Mod;
		for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
		if (hp == NULL) {
			hd[u].v = val[u];
			hd[u].cur = 0;
			hd[u].next = hash[h];
			hash[h] = &(hd[u]);
		}
		
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (par[w] == 0) {
				par[w] = u;
				val[w] = val[u] ^ p->cost;
				q[tail++] = w;
			}
		}
	}
	
	int size[200001] = {};
	for (head--; head >= 0; head--) {
		u = q[head];
		size[u]++;
		if (head != 0) size[par[u]] += size[u];
	}
	for (u = 1; u <= N; u++) par[u] = -1;
	DFS(adj, 1, par, val, hash);
	
	int k;
	edge *aux[400001] = {}, f[400001];
	for (u = 1, i = 0, k = N; u <= N; u++) {
		if (par[u] == 0) {
			h = val[u] % H_Mod;
			for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->v == val[u]) break;
			if (hp->cur == 0) hp->cur = ++k;
			f[i].v = u;
			f[i].next = aux[hp->cur];
			aux[hp->cur] = &(f[i++]);
		} else {
			f[i].v = u;
			f[i].next = aux[par[u]];
			aux[par[u]] = &(f[i++]);
		}
	}
	
	for (u = 2; u <= N; u++) par[u] = 0;
	par[1] = 1;
	q[0] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (par[w] == 0) {
				par[w] = u;
				q[tail++] = w;
			}
		}
	}
	
	int j;
	long long ans = 0, tmp;
	edge *pp;
	for (i = N + 1; i <= k; i++) {
		for (p = aux[i], j = 0, tmp = N, tail = 0; p != NULL; p = p->next, j++) {
			w = p->v;
			tmp -= size[w];
			q[tail++] = w;
		}
		ans += tmp * j;
		for (head = 0; head < tail; head++) {
			u = q[head];
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				if (w == par[u]) continue;
				for (pp = aux[w], j = 0, tmp = size[w]; pp != NULL; pp = pp->next, j++) {
					tmp -= size[pp->v];
					q[tail++] = pp->v;
				}
				ans += tmp * (j + 1);
			}
		}
	}
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}
0