結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-09-06 14:15:03 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 106 ms / 3,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 954 ms |
コンパイル使用メモリ | 30,208 KB |
実行使用メモリ | 36,820 KB |
最終ジャッジ日時 | 2024-06-23 21:21:44 |
合計ジャッジ時間 | 3,295 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.c: In function 'in': main.c:12:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 12 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:18:24: note: in expansion of macro 'gc' 18 | int n = 0, c = gc(); | ^~
ソースコード
// yukicoder: 872 All Tree Path// 2019.9.6 bal4u#include <stdio.h>#include <stdlib.h>#include <string.h>typedef long long ll;//// 高速入力#if 1#define gc() getchar_unlocked()#else#define gc() getchar()#endifint in() { // 非負整数の入力int n = 0, c = gc();do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');return n;}int N;int hi[200005], *to[200005], *w[200005];int f[200005];ll ans;void dfs(int now, int par) {int i, j;f[now] = 1;for (i = 0; i < hi[now]; i++) if ((j = to[now][i]) != par) {dfs(j, now);ans += ((ll)w[now][i] * f[j] * (N-f[j])) << 1;f[now] += f[j];}}int main(){int i, k, u, v;int *memo, sz;N = in();memo = malloc(N*sizeof(int)*3);sz = 0; for (i = 1; i < N; i++) {u = in()-1, v = in()-1;memo[sz++] = u, memo[sz++] = v, memo[sz++] = in();hi[u]++, hi[v]++;}for (i = 0; i < N; i++) if (hi[i]) {to[i] = malloc(hi[i] * sizeof(int));w[i] = malloc(hi[i] * sizeof(int));}memset(hi, 0, sizeof(int)*N);i = 0; while (i < sz) {u = memo[i++], v = memo[i++];k = hi[u]++, to[u][k] = v, w[u][k] = memo[i];k = hi[v]++, to[v][k] = u, w[v][k] = memo[i++];}dfs(0, -1);printf("%lld\n", ans);return 0;}