제출 #405060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405060		BERNARB01	Duathlon (APIO18_duathlon)	C++17	8 / 100	36 ms	3532 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

struct dsu {
	int nCC;
	vector<int> pr, sz, rank, edges;
	dsu(int n) {
		nCC = n;
		pr.resize(n);
		sz.assign(n, 1);
		edges.assign(n, 0);
		rank.assign(n, 1);
		iota(pr.begin(), pr.end(), 0);
	}
	int fnd(int u) {
		if (u == pr[u]) {
			return u;
		}
		pr[u] = fnd(pr[u]);
		return pr[u];
	}
	bool unate(int u, int v) {
		u = fnd(u); v = fnd(v);
		if (u == v) {
			edges[u]++;
			return false;
		}
		--nCC;
		if (rank[u] > rank[v]) {
			swap(u, v);
		}
		pr[u] = v;
		rank[v] += (rank[u] == rank[v]);
		sz[v] += sz[u];
		edges[v] += 1 + edges[u];
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	dsu se(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		se.unate(u, v);
	}
	vector<int> vis(n, 0);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int P = se.fnd(i);
		if (!vis[P]) {
			vis[P] = 1;
			if (se.sz[P] > 2) {
				if (se.edges[P] == se.sz[P]) {
					ans += se.sz[P] * 1LL * (se.sz[P] - 1) * (se.sz[P] - 2);
				} else {
					ans += se.sz[P] * 1LL * (se.sz[P] - 1) * (se.sz[P] - 2) / 3;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10