제출 #1262778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262778		bot1132	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	968 ms	64908 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define si(x) int(x.size())
template<class t>using vc=vector<t>;
using pl=pair<ll,ll>;

ll n,m,par[100005],sz[100005],ans;
set<ll>in[100005],ins[100005];
set<pl>out[100005];
queue<pl>mg;
ll find(ll x){
	if(x==par[x])return x;
	return par[x]=find(par[x]);
}
void unite(ll x,ll y){
	x=find(x);
	y=find(y);
	par[y]=x;
	sz[x]+=sz[y];
}
void erase_edge(ll a,ll b){
	b=find(b);
	out[find(a)].erase(mp(a,b));
	in[b].erase(a);
}
bool add_edge(ll a,ll b){
	b=find(b);
	ll p=find(a);
	if(p==b||out[p].find(mp(a,b))!=out[p].end())return false;
	in[b].insert(a);
	out[p].insert(mp(a,b));
	ins[b].insert(p);
	if(ins[p].find(b)!=ins[p].end())mg.push(mp(p,b));
	return true;
}
ll cnt_edge(ll x){
	return sz[x]*(sz[x]-1LL)+ll(si(in[x]))*sz[x];
}
void mrg(ll x,ll y){
	if(si(in[x])+si(out[x])<si(in[y])+si(out[y]))swap(x,y);
	ans-=cnt_edge(x);
	ans-=cnt_edge(y);
	vc<pl>erase;
	vc<pl>add;
	for(auto &i:in[y]){
		erase.pb(mp(i,y));
		if(find(i)!=x)add.pb(mp(i,y));
	}
	for(auto &i:out[y]){
		erase.pb(mp(i.F,i.S));
		if(i.S!=x)add.pb(mp(i.F,i.S));
	}
	for(auto &i:erase)erase_edge(i.F,i.S);
	unite(x,y);
	for(auto &i:add)add_edge(i.F,i.S);
	ans+=cnt_edge(x);
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		par[i]=i;
		sz[i]=1;
	}
	while(m--){
		ll a,b;
		cin>>a>>b;
		a--,b--;
		if(add_edge(a,b)){
			ans+=sz[find(b)];
		}
		while(!mg.empty()){
			ll x=find(mg.front().F),y=find(mg.front().S);
			mg.pop();
			if(x!=y)mrg(x,y);
		}
		cout<<ans<<endl;
	}
}

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83