Submission #877035

#	Time	Username	Problem	Language	Result	Execution time	Memory
877035		parsadox2	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	1 ms	4952 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 , M = 3e5 + 10;
int n , m;
long long fin_ans = 0;

struct DSU{
	set <int> st[N];
	int sz[N] , par[N];
	void Build()
	{
		for(int i = 1 ; i <= n ; i++)
		{
			sz[i] = 1;
			st[i].insert(i);
		}
	}
	int root(int v)
	{
		return (par[v] == 0 ? v : par[v] = root(par[v]));
	}
	void Merge(int a , int b)
	{
		fin_ans -= 1LL * sz[a] * ((long long)st[a].size() - 1);
		fin_ans -= 1LL * sz[b] * ((long long)st[b].size() - 1);
		if(sz[a] > sz[b])
			swap(a , b);
		for(auto u : st[a])
			st[b].insert(u);
		st[a].clear();
		par[a] = b;
		sz[b] += sz[a];
		fin_ans += 1LL * sz[b] * ((long long)st[b].size() - 1);
	}
	void Add(int a , int b)
	{
		int ra = root(a) , rb = root(b);
		if(st[ra].find(b) != st[ra].end())
			return;
		if(st[rb].find(a) != st[rb].end())
		{
			Merge(ra , rb);
			return;
		}
		st[ra].insert(b);
		fin_ans += sz[ra];
	}
} dsu;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);   cout.tie(0);
	cin >> n >> m;
	dsu.Build();
	while(m--)
	{
		int u , v;  cin >> u >> v;
		dsu.Add(v , u);
		cout << fin_ans << '\n';
	}
	return 0;
}

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