Submission #221654

#	Time	Username	Problem	Language	Result	Execution time	Memory
221654		Andrei_Cotor	Making Friends on Joitter is Fun (JOI20_joitter2)	C++11	0 / 100	11 ms	12160 KiB

joitter2

#include<iostream>
#include<vector>
#include<set>
#include<deque>

using namespace std;

int P[100005];
vector<int> Elements[100005];
set<int> Followers[100005];
set<int> GroupFollows[100005];

int parent(int x)
{
	int _x=x;
	while(P[x]!=0)
		x=P[x];

	while(P[_x]!=0)
	{
		int aux=P[_x];
		P[_x]=x;
		_x=aux;
	}
	return x;
}

long long rez;
void unite(int x, int y)
{
	rez=rez-1LL*Elements[x].size()*(Elements[x].size()-1);
	rez=rez-1LL*Elements[y].size()*(Elements[y].size()-1);
	rez=rez-1LL*Elements[x].size()*Followers[x].size();
	rez=rez-1LL*Elements[y].size()*Followers[y].size();

	for(auto el:Elements[y])
	{
		Followers[x].erase(el);
		Elements[x].push_back(el);
	}

	for(auto follower:Followers[y])
	{
		int pf=parent(follower);
		if(pf!=x)
		{
			GroupFollows[pf].erase(y);
			GroupFollows[pf].insert(x);
			Followers[x].insert(follower);
		}
	}

	GroupFollows[x].erase(y);
	GroupFollows[y].erase(x);
	for(auto gf:GroupFollows[y])
		GroupFollows[x].insert(gf);

	P[y]=x;
	rez=rez+1LL*Elements[x].size()*(Elements[x].size()-1);
	rez=rez+1LL*Elements[x].size()*Followers[x].size();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n,m;
	cin>>n>>m;

	for(int i=1; i<=n; i++)
		Elements[i].push_back(i);

	rez=0;
	for(int i=1; i<=m; i++)
	{
		int x,y;
		cin>>x>>y;
		int px=parent(x);
		int py=parent(y);

		if(px==py)
		{
			cout<<rez<<"\n";
			continue;
		}

		if(Followers[py].find(x)==Followers[py].end())
		{
			rez+=Elements[py].size();
			Followers[py].insert(x);
		}

		GroupFollows[px].insert(py);

		deque<pair<int,int> > Q;
		if(GroupFollows[py].find(px)!=GroupFollows[py].end())
			Q.push_back({px,py});

		while(!Q.empty())
		{
			int _x=parent(Q.front().first);
			int _y=parent(Q.front().second);
			Q.pop_front();

			if(Elements[_x].size()<Elements[_y].size())
				swap(_x,_y);

			if(_x==_y)
				continue;

			unite(_x,_y);

			for(auto gf:GroupFollows[_y])
			{
				if(Followers[_x].find(gf)!=Followers[_x].end())
					Q.push_back({_x,gf});
			}

			for(auto follower:Followers[_y])
			{
				int pf=parent(follower);
				if(pf!=_x && GroupFollows[_x].find(pf)!=GroupFollows[_x].end())
					Q.push_back({_x,pf});
			}
		}

		cout<<rez<<"\n";
	}
	return 0;
}

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