Submission #111862

#	Time	Username	Problem	Language	Result	Execution time	Memory
111862		square1001	Duathlon (APIO18_duathlon)	C++14	10 / 100	1137 ms	1020924 KiB

count_triplets

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int> > G(N);
	for(int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> C(N), P(N), R(N);
	function<void(int, int, int)> dfs = [&](int pos, int pre, int root) {
		P[pos] = pre;
		C[pos] = 1;
		R[pos] = root;
		for(int i : G[pos]) {
			if(i == pre) continue;
			dfs(i, pos, root);
			C[pos] += C[i];
		}
	};
	for(int i = 0; i < N; ++i) {
		if(C[i] == 0) {
			dfs(i, -1, i);
		}
	}
	long long ans = 0;
	for(int i = 0; i < N; ++i) {
		int rem = C[R[i]] - 1;
		long long sum = rem * (rem - 1);
		for(int j : G[i]) {
			if(j == P[i]) continue;
			rem -= C[j];
			sum -= 1LL * C[j] * (C[j] - 1);
		}
		sum -= 1LL * rem * (rem - 1);
		ans += sum;
	}
	cout << ans << endl;
	return 0;
}

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