結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー edon8618
提出日時 2025-07-11 22:59:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,517 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 202,540 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2025-07-11 23:00:09
合計ジャッジ時間 13,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 5 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep(i,r) for(ll i=0;i<(ll)r;i++)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)



// ll inf=(1ll<<62);

// ll rui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a*rui(a*a,b/2);
//     return rui(a*a,b/2);
// }

// ll const mod=998244353ll;
// ll modrui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a%mod*modrui(a%mod*a%mod,b/2)%mod;
//     return modrui(a%mod*a%mod,b/2)%mod;
// }

// ll inv(ll x){
//     return modrui(x,mod-2);
// }


vl par(2<<17,-1);

ll root(ll x){
    if(par[x]<0)return x;
    else return par[x]=root(par[x]);
}

ll sz(ll x){
    x=root(x);
    return -par[x];
}

bool same(ll x,ll y){
    if(root(x)==root(y))return true;
    else return false;
}

void unite(ll x,ll y){
    if(same(x,y))return;
    x=root(x);
    y=root(y);
    if(x>y)swap(x,y);
    par[x]+=par[y];
    par[y]=x;
}


void solve(){
    ll n,m;cin >> n >> m;
    vl u(m),v(m);
    rep(i,m){
        cin >> u[i] >> v[i];
        if(u[i]>v[i])swap(u[i],v[i]);
    }
    ll q;cin >> q;
    vl b(q);
    rep(i,q){
        cin >> b[i];
        b[i]--;
    }
    vb ok(q,1);
    rep(i,q)ok[b[i]]=0;

    // ll all=n*(n-1)/2;
    rep(i,q){
        if(ok[i]){
            // if(same(u[i],v[i]))continue;
            // all+=sz(u[i])*(sz(u[i])-1)/2+sz(v[i])*(sz(v[i])-1)/2;

            unite(u[i],v[i]);
            // all-=sz(u[i])*(sz(u[i])-1)/2;;
        }
    }

    // cout << "sz" << endl;
    // rep(i,n)cout << sz(i+1) << " ";
    // return;

    vl ans(q,0);
    reverse(b.begin(),b.end());
    rep(i,q){
        if(same(u[b[i]],v[b[i]]))continue;
        ans[i]-=sz(u[b[i]])*(sz(u[b[i]])-1)/2+sz(v[b[i]])*(sz(v[b[i]])-1)/2;
        unite(u[b[i]],v[b[i]]);
        // cout << sz(u[b[i]]);
        ans[i]+=sz(u[b[i]])*(sz(u[b[i]])-1)/2;
    }
    // cout << "ans" << endl;
    // rep(i,q)cout << ans[i] << " ";
    // cout << endl;
    reverse(ans.begin(),ans.end());
    rep(i,q-1)ans[i+1]+=ans[i];
    

    vb used(2<<17,0);
    ll all=n*(n-1)/2;
    rep(i,n){
        if(used[root(i+1)])continue;
        used[root(i+1)]=1;
        all-=sz(i+1)*(sz(i+1)-1)/2;
    }


    rep(i,q)cout << all+ans[i] << endl;
}



int main(){
    ll t=1;
    // cin >> t;
    while(t--)solve();
}
0