結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 23:16:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 3,427 bytes |
コンパイル時間 | 2,251 ms |
コンパイル使用メモリ | 207,868 KB |
実行使用メモリ | 13,244 KB |
最終ジャッジ日時 | 2025-07-11 23:16:17 |
合計ジャッジ時間 | 8,849 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main(void) { ll n,m; cin>>n>>m; vector<pair<ll,ll>> edge; rep(i,m) { ll v,u; cin>>u>>v; u--; v--; edge.emplace_back(u,v); } ll q; cin>>q; vector<ll> col(q); rep(i,q) { ll b; cin>>b; b--; col[i]=b; } UnionFind uf(n); vector<bool> ers(m); rep(i,q) { ers[col[i]]=true; } rep(i,m) { if(!ers[i]) uf.unite(edge[i].first,edge[i].second); } ll total=n*(n-1)/2; ll reach=0; rep(i,n) { if(uf.root(i)==i){ ll sz=uf.szof(i); reach+=sz*(sz-1)/2ll; } } ll unr=total-reach; vl ans(q); irep(i,q-1,0) { ans[i]=unr; ll collap=col[i]; ll u=edge[collap].first,v=edge[collap].second; if(!uf.same(u,v)){ ll su=uf.szof(u); ll sv=uf.szof(v); uf.unite(u,v); unr-=(ll)su*(ll)sv; } } rep(i,q) { cout<<ans[i]<<nl; } } /////// library zone /////// #else #include <bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<n;i++) #define srep(i,l,r) for(ll i=l;i<=r;i++) #define irep(i,r,l) for(ll i=r;i>=l;i--) using ll = long long; using ld = long double; const ll mod=998244353; #define vout(v) for(auto i :v) cout<<i<<" "; #define INF 9223300000000000000ll #define Winf 5e12 #define nl "\n" #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define vl vector<ll> #define vc vector<char> #define pb push_back ll vecmax(vector<ll> a) { ll ans=-INF; rep(i,(ll)a.size()) { ans=max(ans,a[i]); } return ans; } struct UnionFind { vector<int> par; vector<int> rank; vector<ll> size; int count; UnionFind(int N):par(N),rank(N,0),count(N),size(N,1){ rep(i,N) { par[i]=i; rank[i]=0; size[i]=1; } } //経路圧縮 int root(int x){ return par[x]==x?x:par[x]=root(par[x]); } void unite(int x,int y){ int rx=root(x),ry=root(y); if(rx==ry) return; count--; if(rank[rx]<rank[ry]) { par[rx]=ry; size[ry]+=size[rx]; size[rx]=0; } else { par[ry]=rx; if(rank[rx]==rank[ry]) rank[rx]++; size[rx]+=size[ry]; size[ry]=0; } } bool same(int x,int y){ return root(x)==root(y); } int comp_count() const{ return count; } ll szof(int ind) { return size[root(ind)]; } }; ll modpow(ll fl, ll po, ll mode) { // mode: 0=modなし, 1=modあり ll ret=1; if (mode) { while (po>0) { if (po&1) ret=(ret*fl)%mod; fl=(fl*fl)%mod; po>>=1; } } else { while (po>0) { if(po&1) ret*=fl; fl*=fl; po>>=1; } } return ret; } ll op(ll a,ll b) {return max(a,b);} ll e() {return -Winf; } template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} void no() { cout<<"No"<<nl;} void yes() { cout<<"Yes"<<nl;} void yn(bool a) { cout<<(a ? "Yes":"No")<<nl; } ll sum(vl &a) { ll ans=0; rep(i,a.size()) ans+=a[i]; return ans; } #endif