Submission #348091

#	Time	Username	Problem	Language	Result	Execution time	Memory
348091		8e7	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	6 ms	9708 KiB

joitter2

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define maxn 100005
#define ll long long
using namespace std;
set<int> adj[maxn], rev[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 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() < adj[b].size() + rev[b].size()) swap(a, b);
	//cout << a << "  " << b << endl;
	//cout << siz[a] << " " << cnt[b] - siz[a] << " " << siz[b] << " " << cnt[a] - siz[b] << endl;

	ll oa = cnt[a], ob = cnt[b];
	ans += 2 * siz[a] * siz[b] - siz[a] - siz[b];
	vector<pair<int, int> > add;
	for (int v:adj[b]) {
		adj[a].insert(v);
		rev[v].erase(b);
		rev[v].insert(a);
		if (rev[a].find(v) != rev[a].end()) {
			add.push_back(make_pair(a, v));
		}
	}
	for (int v:rev[b]) {
		if (rev[a].find(v) == rev[a].end()) cnt[a] += siz[find(v)];
		rev[a].insert(v);
		adj[v].erase(b);
		adj[v].insert(a);
		if (adj[a].find(v) != adj[a].end()) {
			add.push_back(make_pair(a, v));
		}
	}
	//cnt[a] = rev[a].size();
	//cout << cnt[a] - ob << " " << siz[b] << " " << cnt[a] - oa << " " << siz[a] << endl;
	ans += (cnt[a] - ob) * siz[b] + (cnt[a] - oa) * siz[a];

	Union(a, b);

	for (auto v:add) {
		combine(v.first, v.second);
	}
}
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;
	}
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		a = find(a), b = find(b);
		if (a == b || adj[a].find(b) != adj[a].end()) {
			cout << ans << "\n";
			continue;
		}
		adj[a].insert(b);
		rev[b].insert(a);
		cnt[b] += siz[a];

		ans += siz[b];
		if (adj[b].find(a) != adj[b].end()) {
			combine(a, b);
		}
		cout << ans << "\n";
	}
}

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