提出 #74552879

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vec vector
#define pll pair<ll,ll>
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;

ll far[N * 2],rankk[N * 2],vis[N * 2];
vec<ll> g[N];
bool ok = true;

void init(ll n){
	for(int i = 1 ; i <= 2 * n ; i++){
		far[i] = i;
		rankk[i] = (i <= n ? 1 : 0);
		vis[i] = 0;
	}
}

ll find(ll x){
	return far[x] == x ? x : far[x] = find(far[x]);
}

void solve(){
	ll n,q;cin >> n >> q;
	init(n);
	ll ans = 0;
	while(q--){
		ll u,v;cin >> u >> v;
		ll x = find(u);
		ll y = find(v);
		ll x1 = find(u + n);
		ll y1 = find(v + n);
		if(x == y || !ok){//不符合两个端点的染色不一样
			cout << "-1\n";
			ok = false;
		}else if(x == y1){//两个点已经在一个集合里面
			cout << ans << "\n";
		}else{
			if(vis[x]) ans -= rankk[x],vis[x] = false;
			if(vis[y]) ans -= rankk[y],vis[y] = false;
			if(vis[x1]) ans -= rankk[x1],vis[x1] = false;
			if(vis[y1]) ans -= rankk[y1],vis[y1] = false;
			//清空合并之前的贡献，加新的贡献，以免贡献重复
			rankk[x] += rankk[y1];
			rankk[y] += rankk[x1];
			far[y1] = x;
			far[x1] = y; 
			if(rankk[x] > rankk[y]){
				ans += rankk[y];
				vis[y]++;
			}else{
				ans += rankk[x];
				vis[x]++;
			}
			cout << ans << "\n";
		}
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int T = 1;
//  	cin >> T;
	while(T--){
		solve();
	}
    return 0;
}

提出情報

ジャッジ結果