結果
問題 | No.1769 Don't Stop the Game |
ユーザー | 👑 ygussany |
提出日時 | 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 |
ソースコード
#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; }