Submission #366353

#	Time	Username	Problem	Language	Result	Execution time	Memory
366353		penguinhacker	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	3 ms	4972 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];
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);

	// 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);
	set<int>().swap(s[b]);
	for (auto it = s[a].begin(); it != s[a].end();) {
		if (find(*it) == a) it = s[a].erase(it);
		else ++it;
	}
}

ll get_ans() {
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		ans += (ll)sz[i] * (sz[i] - 1);
		ans += (ll)s[i].size() * sz[i];
	}
	return ans;
}

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);
			s[find(b)].insert(a);
		}
		cout << get_ans() << "\n";
	}
	return 0;
}

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