結果

問題 No.1769 Don't Stop the Game
ユーザー 👑 ygussany
提出日時 2021-11-13 14:32:57
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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