Submission #877032

# Submission time Handle Problem Language Result Execution time Memory
877032 2023-11-22T18:33:14 Z parsadox2 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
1 ms 5160 KB
#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();
		fin_ans -= 1LL * sz[b] * (long long)st[b].size();
		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();
	}
	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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5160 KB Output isn't correct
2 Halted 0 ms 0 KB -