Submission #467018

#	Time	Username	Problem	Language	Result	Execution time	Memory
467018		prvocislo	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	675 ms	44168 KiB

joitter2

#include <iostream>
#include <vector>
#include <set>
typedef long long ll;
using namespace std;

// a, b, c sa bude pouzivat na vrcholy, x, y, z sa bude pouzivat na komponenty.
const int maxn = 1e5 + 5;
vector<int> p(maxn), siz(maxn, 1);
vector<set<int> > in(maxn); // hrany ktore idu do tohto komponentu
vector<set<pair<int, int> > > out(maxn); // hrany ktore idu z tohto komponentu, pamatame si aj ze z ktoreho vrchola idu
ll ans = 0;
int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
void merge(int a, int b)
{
	int x = root(a), y = root(b);
	if (x == y) return;
	auto it = out[y].lower_bound({ x, -1 });
	if (it != out[y].end() && it->first == x) // potrebujeme spojit x a y
	{
		// chceme mergnut x do y
		if (out[x].size() + in[x].size() > out[y].size() + in[y].size()) swap(x, y);
		vector<pair<int, int> > e;
		for (const pair<int, int> &i : out[x]) // ideme sa pozriet na hrany ktore idu z x do inych vrcholov
		{
			int z = i.first, c = i.second; // (x(c)) -> (z)
			ans -= siz[z];
			in[z].erase(c);
			if (z != y) e.push_back({ c, z }); // tuto hranu budeme musiet znovu skontrolovat a opravit
		}
		ans -= in[x].size() * 1ll * siz[x]; // tieto hrany budeme musiet prerobit, takze zatial zmazeme to co pridavaju
		ans += in[y].size() * 1ll * siz[x]; // hrany ktore isli do y sa teraz mozu rozsirit aj do x
		ans += siz[y] * 2ll * siz[x]; // tieto dva komponenty sa spoja, kazdy vrchol s kazdym
		for (const int& c : in[x])
		{
			int z = root(c); // (z(c)) -> (x)
			out[z].erase({ x, c });
			if (z != y) e.push_back({ c, y });
		}
		in[x].clear(), out[x].clear();
		p[x] = y, siz[y] += siz[x];
		for (const pair<int, int>& i : e)
			merge(i.first, i.second);
	}
	else if (!in[y].count(a))
	{
		in[y].insert(a), out[x].insert({ y, a });
		ans += siz[y];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = 0, a, b; i < m; i++)
	{
		cin >> a >> b;
		merge(a, b);
		cout << ans << "\n";
	}
	return 0;
}

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