oj.uz

답안 #568069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568069 2022-05-24T15:21:05 Z LittleCube 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 5 ms 9720 KB 
#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())
			f[b].swap(f[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())
			f[b].swap(f[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";
			fd[find(B)].insert(A);
			f[find(A)].insert(B);
			ans += rk[find(B)];
			if(f[find(B)].find(A) != f[find(B)].end())
				chain.emplace_back(pii(A, 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

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

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 5 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 5 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 5 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -