結果
問題 |
No.3087 University Coloring
|
ユーザー |
![]() |
提出日時 | 2025-04-04 22:03:29 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 1,616 bytes |
コンパイル時間 | 2,280 ms |
コンパイル使用メモリ | 27,136 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2025-04-04 22:04:09 |
合計ジャッジ時間 | 5,716 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:76:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%lld %lld", &n, &m); | ^~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:80:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 80 | scanf("%lld %lld %lld", &u[i], &v[i], &w[i]); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> long long int u[200005], v[200005], w[200005]; long long int h[200005], l; long long int comp_h(long long int a, long long int b) { if (w[h[a]] < w[h[b]]) return 1; else return -1; } void swap_h(long long int a, long long int b) { long long int f = h[a]; h[a] = h[b]; h[b] = f; return; } void push(long long int ne) { h[l] = ne; long long int p = l++; for (; p > 0; p = (p - 1) / 2) if (comp_h((p - 1) / 2, p) > 0) swap_h((p - 1) / 2, p); return; } long long int pop() { swap_h(0, --l); long long int p = 0; for (;;) { if (2 * p + 2 < l) { if (comp_h(2 * p + 1, 2 * p + 2) > 0) { if (comp_h(p, 2 * p + 2) > 0) swap_h(p, 2 * p + 2); p = 2 * p + 2; } else { if (comp_h(p, 2 * p + 1) > 0) swap_h(p, 2 * p + 1); p = 2 * p + 1; } } else if (2 * p + 1 < l) { if (comp_h(p, 2 * p + 1) > 0) swap_h(p, 2 * p + 1); p = 2 * p + 1; } else break; } return h[l]; } long long int par[200005]; long long int root(long long int n) { if (par[n] != n) par[n] = root(par[n]); return par[n]; } void uni(long long int a, long long int b) { a = root(a); b = root(b); par[b] = a; return; } int main() { long long int n, m; scanf("%lld %lld", &n, &m); long long int i; for (i = 0; i < m; i++) { scanf("%lld %lld %lld", &u[i], &v[i], &w[i]); u[i]--; v[i]--; } for (i = 0; i < n; i++) par[i] = i; l = 0; for (i = 0; i < m; i++) push(i); long long int ans = 0; while (l > 0) { i = pop(); if (root(u[i]) != root(v[i])) ans += 2 * w[i]; uni(u[i], v[i]); } printf("%lld\n", ans); return 0; }