Submission #389760

#	Time	Username	Problem	Language	Result	Execution time	Memory
389760		ogibogi2004	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	1491 ms	73796 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(comp[b].size()+edges_in[b].size()+edges_out[b].size()>comp[a].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(xd);
		if(edges_out[a].find(t)!=edges_out[a].end())
		{
			merges.push({xd,a});
		}
	}
	for(auto xd:edges_out[b])
	{
		int t=getRoot(xd);
		if(xd==a)
		{
			continue;
		}
		edges_out[a].insert(xd);
		//edges_in[t].erase(b);
		//edges_in[t].insert(a);
		if(edges_out[xd].find(a)!=edges_out[xd].end())
		{
			merges.push({xd,a});
		}
	}
	edges_in[a].erase(b);
	edges_out[a].erase(b);
	for(auto xd:comp[b])
	{
		edges_in[a].erase(xd);
		comp[a].insert(xd);
	}
	par[b]=a;
	sz[a]+=sz[b];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	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,a1,b1;
		cin>>a>>b;a1=a;b1=b;
		a=getRoot(a);
		b=getRoot(b);
		if(a==b)
		{
			cout<<ans<<endl;
			continue;
		}
		else
		{
			if(edges_out[b].find(a)!=edges_out[b].end())
			{
				merges.push({a,b});
				ans-=cnt(a);ans-=cnt(b);
				edges_in[b].insert(a1);
				edges_out[a].insert(b);
				ans+=cnt(a);ans+=cnt(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_out[b].find(a)==edges_out[b].end())
			{
				ans-=cnt(b);
				edges_in[b].insert(a1);
				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;
		}
		/*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<<"**\n";
		for(int j=1;j<=n;j++)
		{
			cout<<getRoot(j)<<":\n";
			for(auto xd:edges_in[getRoot(j)])
			{
				cout<<xd<<" ";
			}
			cout<<endl;
		}*/
	}
return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void merge(int, int)':
joitter2.cpp:44:7: warning: unused variable 't' [-Wunused-variable]
   44 |   int t=getRoot(xd);
      |       ^
joitter2.cpp: In function 'int main()':
joitter2.cpp:80:14: warning: variable 'b1' set but not used [-Wunused-but-set-variable]
   80 |   int a,b,a1,b1;
      |              ^~

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