Submission #389596

#	Time	Username	Problem	Language	Result	Execution time	Memory
389596		ogibogi2004	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	6 ms	9676 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
int n,m;
int par[MAXN];
ll sz[MAXN];
set<int>edges_in[MAXN];
set<int>edges_out[MAXN];
ll ans=0;
int getRoot(int u)
{
	if(u==par[u])return u;
	return par[u]=getRoot(par[u]);
}
ll cnt(int u)
{
	return sz[u]*(sz[u]-1ll)+edges_in[u].size()*sz[u];
}
stack<pair<int,int> >merges;
void merge(int a,int b)
{
	a=getRoot(a);b=getRoot(b);
	if(a==b)return;
	if(edges_in[b].size()+edges_out[b].size()>edges_in[a].size()+edges_out[a].size())swap(a,b);
	for(auto xd:edges_in[b])
	{
		int t=getRoot(xd);
		if(t==a)continue;
		edges_out[t].erase(b);
		edges_out[t].insert(a);
		edges_in[a].insert(t);
		if(edges_out[a].find(t)!=edges_out[a].end())
		{
			merges.push({t,a});
		}
	}
	for(auto xd:edges_out[b])
	{
		int t=getRoot(xd);
		if(t==a)continue;
		edges_out[a].insert(t);
		edges_in[t].erase(b);
		edges_in[t].insert(a);
		if(edges_in[a].find(t)!=edges_in[a].end())
		{
			merges.push({t,a});
		}
	}
	edges_in[a].erase(b);
	edges_out[a].erase(b);
	par[b]=a;
	sz[a]+=sz[b];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		par[i]=i;
		sz[i]=1;
	}
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		a=getRoot(a);
		b=getRoot(b);
		if(a==b)
		{
			cout<<ans<<endl;
			continue;
		}
		else
		{
			if(edges_in[a].find(b)!=edges_in[a].end())
			{
				merges.push({a,b});
				int x,y;
				while(!merges.empty())
				{
					tie(x,y)=merges.top();merges.pop();
					ans-=cnt(getRoot(x));
					ans-=cnt(getRoot(y));
					merge(x,y);
					ans+=cnt(getRoot(x));
					//ans+=cnt(getRoot(y));
				}
			}
			else if(edges_in[b].find(a)==edges_in[b].end())
			{
				edges_in[b].insert(a);
				edges_out[a].insert(b);
				ans+=sz[b];
			}
			cout<<ans<<endl;
		}
	}
return 0;
}

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