Submission #567980

#	Time	Username	Problem	Language	Result	Execution time	Memory
567980		LittleCube	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	2 ms	4948 KiB

joitter2

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, M, dsu[100005], rk[100005];
ll ans;
set<int> fd[100005];

int find(int k)
{
	return k == dsu[k] ? k : dsu[k] = find(dsu[k]);
}


void follow(int a, int b)
{
	if(fd[a].size() <= fd[b].size())
	{
		ll ag = fd[a].size(), bg = fd[b].size();
		for(auto i : fd[a])
		{
			if(fd[b].find(i) != fd[b].end())
				ag--, bg--;
			else fd[b].insert(i);
		}
		ans += ag * rk[b] + bg * rk[a];
		if(rk[a] <= rk[b])
		{
			dsu[a] = b;
			rk[b] += rk[a];
		}
		else 
		{
			dsu[b] = a;
			rk[a] += rk[b];
			fd[a].swap(fd[b]);
		}

	}
	else follow(b, a);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++)
	{
		dsu[i] = i, rk[i] = 1;
		fd[i].insert(i);
	}
	for(int i = 1; i <= M; i++)
	{
		int A, B;
		cin >> A >> B;
		if(find(A) == find(B));
		else if(fd[find(B)].find(A) != fd[find(B)].end());
		else if(fd[find(A)].find(B) != fd[find(A)].end())
		{	
			//cout << "mergeeee\n";
			follow(find(A), find(B));
		}
		else
		{
			//cout << "simple follow\n";
			fd[find(B)].insert(A);
			ans += rk[find(B)];
		}
		cout << ans << '\n';
	}
}

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