Submission #64924

#	Time	Username	Problem	Language	Result	Execution time	Memory
64924		gusfring	Duathlon (APIO18_duathlon)	C++14	23 / 100	1193 ms	865736 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
typedef long long ll;
int sz[MAXN], N, M, vis[MAXN], S;
ll res;
vector<int> adj[MAXN];

void dfs(int u, int p){
	vis[u] = 1, sz[u] = 1;
	for(int v : adj[u])
		if(v != p){ dfs(v, u); sz[u] += sz[v]; }
}

void solve(int u, int p){
	vector<int> vec;
	if(p != -1) vec.push_back(S - sz[u]);
	for(int v : adj[u])
		if(v != p){
			vec.push_back(sz[v]);
			solve(v, u);
		}
	int sum = 0;
	for(int x : vec){
		res += 1LL * sum * x;
		sum += x;
	}
}

int main(){
	scanf("%d %d", &N, &M);
	while(M--){
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=N; ++i)
		if(!vis[i]){
			dfs(i, -1);
			S = sz[i];
			solve(i, -1);
		}
	printf("%lld\n", 2 * res);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

• 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