Submission #59308

#	Time	Username	Problem	Language	Result	Execution time	Memory
59308		thiago4532	Duathlon (APIO18_duathlon)	C++17	23 / 100	164 ms	17472 KiB

count_triplets

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5 + 10, inf = 0x3f3f3f3f;
vector<int> grafo[maxn];
int sz[maxn];
int mark[maxn];
bool test[maxn];

void dfs(int u, int p=0){
	if(mark[u]) return;
	mark[u] = true;

	sz[u] = 1;
	for(auto v : grafo[u]){
		if(v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

int ans;
void solve(int u, int p=0, int acc=0){
	if(test[u]) return;
	test[u] = true;

	ans += (2 * acc * (sz[u] - 1));

	for(auto v : grafo[u]){
		if(v == p) continue;
		ans += (sz[u] - sz[v] - 1) * sz[v];
		solve(v, u, sz[u] - sz[v] + acc);
	}
}

main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}

	for(int i=1;i<=n;i++)
		dfs(i);

	for(int i=1;i<=n;i++)
		solve(i);	

	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

count_triplets.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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