結果

問題 No.1769 Don't Stop the Game
ユーザー ygussanyygussany
提出日時 2021-11-13 14:32:57
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 154 ms / 3,000 ms
コード長 2,915 bytes
コンパイル時間 546 ms
コンパイル使用メモリ 33,132 KB
実行使用メモリ 46,596 KB
最終ジャッジ日時 2024-06-29 18:04:52
合計ジャッジ時間 4,093 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
21,764 KB
testcase_01 AC 5 ms
21,740 KB
testcase_02 AC 5 ms
22,904 KB
testcase_03 AC 5 ms
21,708 KB
testcase_04 AC 5 ms
21,780 KB
testcase_05 AC 4 ms
22,912 KB
testcase_06 AC 5 ms
21,868 KB
testcase_07 AC 5 ms
22,784 KB
testcase_08 AC 85 ms
30,976 KB
testcase_09 AC 64 ms
30,776 KB
testcase_10 AC 96 ms
30,808 KB
testcase_11 AC 59 ms
27,004 KB
testcase_12 AC 108 ms
33,012 KB
testcase_13 AC 114 ms
31,100 KB
testcase_14 AC 116 ms
30,976 KB
testcase_15 AC 114 ms
31,100 KB
testcase_16 AC 117 ms
30,976 KB
testcase_17 AC 126 ms
33,152 KB
testcase_18 AC 132 ms
30,980 KB
testcase_19 AC 154 ms
31,104 KB
testcase_20 AC 152 ms
30,976 KB
testcase_21 AC 152 ms
31,104 KB
testcase_22 AC 148 ms
30,972 KB
testcase_23 AC 103 ms
29,060 KB
testcase_24 AC 108 ms
28,928 KB
testcase_25 AC 55 ms
28,928 KB
testcase_26 AC 74 ms
30,976 KB
testcase_27 AC 79 ms
46,596 KB
testcase_28 AC 94 ms
46,596 KB
testcase_29 AC 88 ms
38,916 KB
testcase_30 AC 87 ms
40,832 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