제출 #221941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221941		Andrei_Cotor	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	0 / 100	15 ms	16768 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];
set<int> NF[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()*NF[x].size();
	rez=rez-1LL*Elements[y].size()*NF[y].size();

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

	Followers[x].erase(y);
	Followers[y].erase(x);
	GroupFollows[x].erase(y);
	GroupFollows[y].erase(x);

	for(auto follower:Followers[y])
	{
		GroupFollows[follower].erase(y);
		GroupFollows[follower].insert(x);
	}

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

	for(auto nf:NF[y])
	{
		if(parent(nf)!=x)
			NF[x].insert(nf);
	}

	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()*NF[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(NF[py].find(x)==NF[py].end())
		{
			rez+=Elements[py].size();
			Followers[py].insert(px);
			NF[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])
			{
				if(follower!=_x && GroupFollows[_x].find(follower)!=GroupFollows[_x].end())
					Q.push_back({_x,follower});
			}
		}

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

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