結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 21:37:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,038 bytes |
コンパイル時間 | 5,598 ms |
コンパイル使用メモリ | 287,040 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2025-07-11 21:38:05 |
合計ジャッジ時間 | 7,582 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 WA * 1 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll =long long; #include<atcoder/dsu> using namespace atcoder; void solve(){ ll N,M; cin>>N>>M; vector<ll> E(M,1e18); vector<array<ll,2>> D(M); for(int i=0;i<M;i++){ ll u,v; cin>>u>>v; D[i]={u-1,v-1}; } ll Q; cin>>Q; vector<ll> H(Q); for(int q=0;q<Q;q++){ cin>>H[q]; H[q]--; E[H[q]]=q; } dsu d(N); ll mg=0; for(int i=0;i<M;i++){ if(E[i]>1e17){ auto [u,v]=D[i]; if(d.same(u,v))continue; mg+=d.size(u)*d.size(v); d.merge(u,v); } } vector<ll> AN(Q); for(int q=Q-1;q>=0;q--){ AN[q]=N*(N-1)/2-mg; auto [u,v]=D[H[q]]; if(d.same(u,v))continue; mg+=d.size(u)*d.size(v); d.merge(u,v); } for(int q=0;q<Q;q++){ cout<<AN[q]<<"\n"; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; // cin>>T; while(T--)solve(); }