結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:18:39 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,249 bytes |
コンパイル時間 | 886 ms |
コンパイル使用メモリ | 27,984 KB |
実行使用メモリ | 12,556 KB |
最終ジャッジ日時 | 2025-07-11 22:18:44 |
合計ジャッジ時間 | 4,519 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:27:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | scanf("%lld %lld", &n, &m); | ^~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:31:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 31 | scanf("%lld %lld", &u[i], &v[i]); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:36:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf("%lld", &q); | ^~~~~~~~~~~~~~~~~ main.c:38:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%lld", &b[i]); | ^~~~~~~~~~~~~~~~~~~~
ソースコード
#include<stdio.h> long long int u[200005], v[200005]; long long int b[200005]; long long int use[200005]; long long int par[200005], cnt[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); if (a != b) { par[b] = a; cnt[a] += cnt[b]; } return; } long long int ans[200005]; 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", &u[i], &v[i]); u[i]--; v[i]--; } long long int q; scanf("%lld", &q); for (i = 0; i < q; i++) scanf("%lld", &b[i]); for (i = 0; i < n; i++) { par[i] = i; cnt[i] = 1; } for (i = 0; i < m; i++) use[i] = 0; for (i = 0; i < q; i++) use[--b[i]]++; long long int res = n * (n - 1) / 2; for (i = 0; i < m; i++) { if (use[i] > 0) continue; if (root(u[i]) != root(v[i])) { res -= cnt[root(u[i])] * cnt[root(v[i])]; uni(u[i], v[i]); } } for (i = q - 1; i >= 0; i--) { ans[i] = res; if (root(u[b[i]]) != root(v[b[i]])) { res -= cnt[root(u[b[i]])] * cnt[root(v[b[i]])]; uni(u[b[i]], v[b[i]]); } } for (i = 0; i < q; i++) printf("%lld\n", ans[i]); return 0; }