제출 #568240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568240		LittleCube	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	100 / 100	1515 ms	159568 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], fdr[100005], fr[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 (fr[a].size() <= fdr[b].size())
		query(fr[a], fdr[b], a);
	else
		query(fdr[b], fr[a], a);

	if (fr[b].size() <= fdr[a].size())
		query(fr[b], fdr[a], a);
	else
		query(fdr[a], fr[b], a);

	if (rk[a] <= rk[b])
		for (int i : fdr[a])
		{
			fr[i].erase(a);
			fr[i].insert(b);
		}
	else
		for (int i : fdr[b])
		{
			fr[i].erase(b);
			fr[i].insert(a);
		}

	if (rk[a] <= rk[b])
		for (int i : fr[a])
		{
			fdr[i].erase(a);
			fdr[i].insert(b);
		}
	else
		for (int i : fr[b])
		{
			fdr[i].erase(b);
			fdr[i].insert(a);
		}
	// cout << fd[a].size() << " " << fd[b].size() << " ";
	ans -= fd[a].size() * rk[a] + fd[b].size() * rk[b];

	if (fd[a].size() <= fd[b].size())
		Merge(fd[a], fd[b]);
	else
		Merge(fd[b], fd[a]);

	if (fdr[a].size() <= fdr[b].size())
		Merge(fdr[a], fdr[b]);
	else
		Merge(fdr[b], fdr[a]);

	if (f[a].size() <= f[b].size())
		Merge(f[a], f[b]);
	else
		Merge(f[b], f[a]);

	if (fr[a].size() <= fr[b].size())
		Merge(fr[a], fr[b]);
	else
		Merge(fr[b], fr[a]);
	// cout << max(fd[a].size(), fd[b].size()) << '\n';
	ans += max(fd[a].size(), fd[b].size()) * (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]);
		if (fr[a].size() >= fr[b].size())
			fr[a].swap(fr[b]);
		if (fdr[a].size() >= fdr[b].size())
			fdr[b].swap(fdr[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]);
		if (fr[a].size() <= fr[b].size())
			fr[a].swap(fr[b]);
		if (fdr[a].size() <= fdr[b].size())
			fdr[b].swap(fdr[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);
		fdr[i].insert(i);
		fr[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 (fr[find(B)].find(find(A)) != fr[find(B)].end())
				chain.emplace_back(pii(A, B));

			fd[find(B)].insert(A);
			f[find(A)].insert(B);
			fdr[find(B)].insert(find(A));
			fr[find(A)].insert(find(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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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