Submission #389699

#	Time	Username	Problem	Language	Result	Execution time	Memory
389699		ogibogi2004	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	9 ms	14392 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];
set<int>comp[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);
	for(auto xd:comp[b])
	{
		edges_in[a].erase(xd);
		edges_out[a].erase(xd);
		comp[a].insert(xd);
	}
	par[b]=a;
	sz[a]+=sz[b];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		par[i]=i;comp[i].insert(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();
					x=getRoot(x);y=getRoot(y);
					if(x!=y)
					{
						ans-=cnt(x);
						ans-=cnt(y);
						merge(x,y);
						ans+=cnt(getRoot(x));
					}
					//ans+=cnt(getRoot(y));
				}
			}
			else if(edges_in[b].find(a)==edges_in[b].end())
			{
				ans-=cnt(b);
				edges_in[b].insert(a);
				edges_out[a].insert(b);
				ans+=cnt(b);
			}
			/*for(int j=1;j<=n;j++)
			{
				cout<<getRoot(j)<<" ";
			}
			cout<<endl;
			for(int j=1;j<=n;j++)
			{
				cout<<cnt(getRoot(j))<<" ";
			}
			cout<<endl;
			cout<<ans<<endl;
			*/
			ll sum=0;
			for(int j=1;j<=n;j++)
			{
				if(j==getRoot(j))
				{
					sum+=cnt(j);
				}
			}
			cout<<sum<<endl;
		}
	}
return 0;
}

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