結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-12 03:09:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,268 bytes |
コンパイル時間 | 1,496 ms |
コンパイル使用メモリ | 118,452 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-12 03:09:28 |
合計ジャッジ時間 | 10,014 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | WA * 20 |
ソースコード
#include <iostream> #include <vector> #include <stack> #include <atcoder/dsu> int main() { int N, M; std::cin >> N >> M; std::vector<int> U(M), V(M); std::vector<bool> usable(M, true); for (int i = 0; i < M; i++) { int u, v; std::cin >> u >> v; u--; v--; U[i] = u; V[i] = v; } int Q; std::cin >> Q; std::stack<int> queries; while (Q--) { int B; std::cin >> B; B--; queries.push(B); usable[B] = false; } atcoder::dsu dsu(N); for (int i = 0; i < M; i++) { if (usable[i]) dsu.merge(U[i], V[i]); } int64_t count = 0; std::stack<int64_t> output; for (int i = 0; i < N; i++) { if (dsu.leader(i) == i) count += dsu.size(i) * int64_t(dsu.size(i) - 1) / 2; } output.push(count); while (!queries.empty()) { int i = queries.top(); queries.pop(); if (dsu.same(U[i], V[i])) { output.push(count); } else { count += int64_t(dsu.size(U[i])) * dsu.size(V[i]); dsu.merge(U[i], V[i]); } } while (!output.empty()) { std::cout << N * int64_t(N - 1) / 2 - output.top() << std::endl; output.pop(); } }