Submission #877056

#	Time	Username	Problem	Language	Result	Execution time	Memory
877056		parsadox2	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1205 ms	77608 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] , in[N] , out[N];
	int sz[N] , par[N];
	void Build()
	{
		for(int i = 1 ; i <= n ; i++)
		{
			sz[i] = 1;
			st[i].insert(i);
			in[i].insert(i);
			out[i].insert(i);
		}
	}
	int root(int v)
	{
		return (par[v] == 0 ? v : par[v] = root(par[v]));
	}
	bool Check(int a , int b)
	{
		if(out[a].find(b) != out[a].end() && in[a].find(b) != in[a].end())
			return true;
		return false;
	}
	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);
		vector <int> tmp;
		for(auto u : out[a])   if(u != a && u != b)
		{
			in[u].erase(a);
			out[b].insert(u);
			in[u].insert(b);
			tmp.push_back(u);		
		}
		for(auto u : in[a])  if(u != a && u != b)
		{
			out[u].erase(a);
			in[b].insert(u);
			out[u].insert(b);
			tmp.push_back(u);
		}
		st[a].clear();
		in[a].clear();
		out[a].clear();
		par[a] = b;
		sz[b] += sz[a];
		fin_ans += 1LL * sz[b] * ((long long)st[b].size() - 1);
		for(auto u : tmp)  if(root(b) != root(u) && Check(root(b) , root(u)))
			Merge(root(b) , root(u));
	}
	void Add(int a , int b)
	{
		int ra = root(a) , rb = root(b);
		if(st[ra].find(b) != st[ra].end())
			return;
		st[ra].insert(b);
		out[ra].insert(rb);
		in[rb].insert(ra);
		fin_ans += sz[ra];
		if(Check(ra , rb))
		{
			Merge(ra , rb);
			return;
		}
	}
} 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: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83