Submission #568085

#	Time	Username	Problem	Language	Result	Execution time	Memory
568085		LittleCube	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5 ms	9724 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], f[100005];

vector<pii> chain;

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

void Merge(set<int> &small, set<int> &big)
{
	for(int i : small)
		big.insert(i);
}

void query(set<int> &small, set<int> &big, int another)
{
	for(int i : small)
		if(big.find(i) != big.end())
			chain.emplace_back(pii(i, another));
}

void follow(int a, int b)
{
	//cout << "merge " << a << " " << b << '\n';
	// out A <-> in B
	if(f[a].size() <= fd[b].size())
		query(f[a], fd[b], a);
	else query(fd[b], f[a], a);
	
	if(f[b].size() <= fd[a].size())
		query(f[b], fd[a], a);
	else query(fd[a], f[b], a);
	
	ll ag = fd[a].size(), bg = fd[b].size(), rep;
	
	if(fd[a].size() <= fd[b].size())
		Merge(fd[a], fd[b]);
	else Merge(fd[b], fd[a]);
	
	rep = ag + bg - max(fd[a].size(), fd[b].size());
    
	if(f[a].size() <= f[b].size())
		Merge(f[a], f[b]);
	else Merge(f[b], f[a]);
	
	ans += ag * rk[b] + bg * rk[a] - rep * (rk[a] + rk[b]);
	//cout << "update ans " << ans << '\n';
	if(rk[a] <= rk[b])
	{
		dsu[a] = b;
		rk[b] += rk[a];
		if(f[a].size() >= f[b].size())
			f[a].swap(f[b]);
		if(fd[a].size() >= fd[b].size())
			fd[b].swap(fd[a]);
	}
	else 
	{
		dsu[b] = a;
		rk[a] += rk[b];
		fd[a].swap(fd[b]);
		if(f[a].size() <= f[b].size())
			f[a].swap(f[b]);
		if(fd[a].size() <= fd[b].size())
			fd[b].swap(fd[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);
		f[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";
			chain.emplace_back(pii(A, B));
		}
		else
		{
			//cout << "simple follow\n";
			if(f[find(B)].find(A) != f[find(B)].end())
				chain.emplace_back(pii(A, B));
			
			fd[find(B)].insert(A);
			f[find(A)].insert(B);
			ans += rk[find(B)];
		}
		while(!chain.empty())
		{
			auto [a, b] = chain.back();
			chain.pop_back();
			if(find(a) != find(b))
				follow(find(a), find(b));
		}

		cout << ans << '\n';
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:114:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |    auto [a, b] = chain.back();
      |         ^

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