제출 #405098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405098		BERNARB01	Duathlon (APIO18_duathlon)	C++17	8 / 100	78 ms	19216 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);
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		se.unate(u, v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int> vis(n, 0);
	vector<int> done(n, 0);
	vector<int> stk;
	function<int(int, int)> DFS = [&](int u, int p) {
		if (done[u]) {
			int R = 1;
			while (stk.back() != u) {
				stk.pop_back();
				R++;
			}
			return R;
		}
		done[u] = 1;
		stk.push_back(u);
		for (int v : g[u]) {
			if (v != p) {
				int R = DFS(v, u);
				if (R) {
					return R;
				}
			}
		}
		stk.pop_back();
		return 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]) {
					stk.clear();
					long long cycLen = DFS(P, -1);
					if (se.sz[P] - cycLen > 2) {
						ans += (se.sz[P] - cycLen) * 1LL * (se.sz[P] - cycLen - 1) * (se.sz[P] - cycLen - 2) / 3;
					}
					if (se.sz[P] - cycLen > 1) {
						ans += (se.sz[P] - cycLen) * 1LL * (se.sz[P] - cycLen - 1) * (cycLen);
					}
					if (se.sz[P] - cycLen > 0) {
						ans += (se.sz[P] - cycLen) * (cycLen - 1) * 2LL * (cycLen) - 2LL * (cycLen - 1);
					}
					ans += (cycLen - 1) * 1LL * (cycLen - 2) * (cycLen);
				} 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