Submission #348316

#	Time	Username	Problem	Language	Result	Execution time	Memory
348316		8e7	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1234 ms	69228 KiB

joitter2

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <queue>
#define maxn 100005
#define ll long long
using namespace std;
set<int> adj[maxn], rev[maxn], chi[maxn];
int par[maxn];
ll siz[maxn], cnt[maxn];
ll ans = 0;
inline int find(int a) {
	return a == par[a] ? a : par[a] = find(par[a]);
}
void Union(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	par[b] = a;
	siz[a] += siz[b];
}
void addEdge(int a, int b);
queue<pair<int, int> > que;
void combine(int a, int b) {
	//cout << a << "  " << b << endl;
	if (find(a) == find(b)) return;
	a = find(a), b = find(b);
	if (adj[a].size() + rev[a].size() + chi[a].size() < adj[b].size() + rev[b].size() + chi[b].size()) swap(a, b);
	//cout << a << "  " << b << endl;
	//cout << siz[a] << " " << chi[b].size() << " " << siz[b] << " " << chi[a].size()<< endl;

	ans += siz[a] * (chi[b].size()) + siz[b] * (chi[a].size());
	adj[a].erase(b);rev[b].erase(a);
	adj[b].erase(a);rev[a].erase(b);
	Union(a, b);
	for (int c:chi[b]) {
		if (chi[a].count(c)) ans -= siz[a];
		else chi[a].insert(c);
	}

	for (int v:adj[b]) {
		rev[v].erase(b);
		addEdge(a, v);
	}
	for (int v:rev[b]) {
		adj[v].erase(b);
		addEdge(v, a);
	}
	adj[b].clear(), rev[b].clear();
	//cnt[a] = rev[a].size();
	//cout << cnt[a] - ob << " " << siz[b] << " " << cnt[a] - oa << " " << siz[a] << endl;
}

void addEdge(int a, int b) {
	adj[a].insert(b);
	rev[b].insert(a);
	if (rev[a].count(b)) {
		que.push(make_pair(a, b));
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		par[i] = i, siz[i] = 1;
		chi[i].insert(i);
	}
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		b = find(b);
		if (find(a) == find(b) || chi[b].count(a)) {
			cout << ans << "\n";
			continue;
		}
		chi[b].insert(a);

		a = find(a);
		ans += siz[b];
		addEdge(a, b);
		while (que.size()) {
			combine(que.front().first, que.front().second);
			que.pop();
		}
		cout << ans << "\n";
	}
}
/*
4 6
1 2
2 3
3 2
1 3
3 4
4 3

 */

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