結果

問題 No.3200 Sinking Islands
ユーザー Andrew8128
提出日時 2025-07-11 22:03:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 1,736 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 91,968 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-07-11 22:03:53
合計ジャッジ時間 6,736 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using std::cerr, std::cin, std::cout, std::endl, std::fixed, std::flush;
#include <vector>
using std::vector;
#include <utility>
using std::make_pair, std::move, std::pair, std::swap, std::tuple;
static_assert(sizeof(long) == 8);
struct UnionFind
{
  vector<long> p;
  UnionFind(long n)
  {
    p.assign(n, -1);
  }
  long find(long x)
  {
    if (p[x] < 0)
    {
      return x;
    }
    return p[x] = find(p[x]);
  }
  bool unite(long x, long y)
  {
    x = find(x);
    y = find(y);
    if (x == y)
    {
      return false;
    }
    if (p[x] > p[y])
    {
      swap(x, y);
    }
    p[x] += p[y];
    p[y] = x;
    return true;
  }
  bool same(long x, long y)
  {
    return (find(x) == find(y));
  }
  long size(long x)
  {
    return -p[find(x)];
  }
};

int main()
{
  long N, M;
  cin >> N >> M;
  vector<long> U(M), V(M);
  for (long i = 0; i < M; i++)
  {
    cin >> U[i] >> V[i];
    U[i]--, V[i]--;
  }
  long Q;
  cin >> Q;
  vector<long> B(Q);
  vector<bool> isBrake(M, false);
  for (long i = 0; i < Q; i++)
  {
    cin >> B[i];
    B[i]--;
    isBrake[B[i]] = true;
  }
  UnionFind uf(N);
  long count = N * (N - 1) / 2;
  for (long i = 0; i < M; i++)
  {
    if (not isBrake[i])
    {
      if (uf.same(U[i], V[i]))
        continue;
      count -= uf.size(U[i]) * uf.size(V[i]);
      uf.unite(U[i], V[i]);
    }
  }
  vector<long> ans(Q);
  for (long i = Q - 1; i >= 0; i--)
  {
    ans[i] = count;
    if (not uf.same(U[B[i]], V[B[i]]))
      count -= uf.size(U[B[i]]) * uf.size(V[B[i]]);
    uf.unite(U[B[i]], V[B[i]]);
  }
  for (long i = 0; i < Q; i++)
  {
    cout << ans[i] << '\n';
  }
  
  return 0;
}
/*
  File : ~/kyopro/yukicoder/554/3200.cpp
  Date : 2025/07/11
  Time : 21:52:00
*/
0