Submission #374599

#	Time	Username	Problem	Language	Result	Execution time	Memory
374599		morato	Duathlon (APIO18_duathlon)	C++17	0 / 100	1146 ms	1048580 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

long long ans;
vector<int> adj[N];
int subtree[N], n;

void dfs(int v, int p = 0) {
	subtree[v] = 1;
	for (int u : adj[v]) if (u != p) {
		dfs(u, v);
		subtree[v] += subtree[u];
	}
	long long aux = (v == 1 ? 0ll :  1ll * (n - subtree[v]));
	vector<long long> pref;
	pref.push_back(aux);
	long long local_ans = 0;
	for (int u : adj[v]) if (u != p) {
		local_ans += pref.back() * subtree[u];
		pref.push_back(pref.back() + subtree[u]);
	}
	ans += 2ll * local_ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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