Submission #366351

#	Time	Username	Problem	Language	Result	Execution time	Memory
366351		penguinhacker	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	4 ms	5100 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 100000;
int n, m, p[mxN], sz[mxN];
ll ans = 0;
set<pair<int, int>> seen;
set<int> s[mxN];

int find(int i) {
	return i == p[i] ? i : p[i] = find(p[i]);
}

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	ans -= (ll)sz[a] * (sz[a] - 1);
	ans -= (ll)sz[b] * (sz[b] - 1);
	ans -= (ll)s[a].size() * sz[a];
	ans -= (ll)s[b].size() * sz[b];

	// now merge them
	p[b] = a;
	sz[a] += sz[b];
	if (s[a].size() < s[b].size()) swap(s[a], s[b]);
	for (const int& i : s[b]) s[a].insert(i);
	for (auto it = s[a].begin(); it != s[a].end();) {
		if (find(*it) == a) it = s[a].erase(it);
		else ++it;
	}
	ans += (ll)sz[a] * (sz[a] - 1);
	ans += (ll)s[a].size() * sz[a];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	fill(sz, sz + n, 1);
	iota(p, p + n, 0);
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		if (seen.count({b, a})) {
			merge(a, b);
		}
		else {
			seen.emplace(a, b);
			b = find(b);
			if (!s[b].count(a)) {
				ans += sz[b];
				s[find(b)].insert(a);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

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