Submission #111867

#	Time	Username	Problem	Language	Result	Execution time	Memory
111867		square1001	Duathlon (APIO18_duathlon)	C++14	31 / 100	204 ms	19320 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);
	vector<bool> vis(N), cycle(N);
	int total = 0, comp = 0;
	function<void(int, int, int)> dfs = [&](int pos, int pre, int root) {
		P[pos] = pre;
		C[pos] = 1;
		R[pos] = root;
		vis[pos] = true;
		++comp;
		for(int i : G[pos]) {
			++total;
			if(vis[i]) continue;
			dfs(i, pos, root);
			C[pos] += C[i];
		}
	};
	for(int i = 0; i < N; ++i) {
		if(C[i] == 0) {
			total = 0, comp = 0;
			dfs(i, -1, i);
			if(comp * 2 == total) {
				cycle[i] = true;
			}
		}
	}
	long long ans = 0;
	for(int i = 0; i < N; ++i) {
		int rem = C[R[i]] - 1;
		long long sum = 1LL * rem * (rem - 1);
		if(!cycle[R[i]]) {
			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: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10