Submission #408028

#	Time	Username	Problem	Language	Result	Execution time	Memory
408028		juggernaut	Duathlon (APIO18_duathlon)	C++17	23 / 100	1122 ms	1048580 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m;
int sz[100005];
vector<int>g[100005];
void dfs(int v,int p){
	sz[v]=1;
	for(int to:g[v])if(to!=p){
		dfs(to,v);
		sz[v]+=sz[to];
	}
}
int root;
ll ans=0;
void calc(int v,int p){
	ll sum=0;
	vector<int>vec;
	for(int to:g[v])if(to!=p)vec.push_back(sz[to]);
	if(root^v)vec.push_back(sz[root]-sz[v]);
	for(int x:vec)sum+=x;
	for(int x:vec){
		sum-=x;
		ans+=1ll*x*sum;
		sum+=x;
	}
	for(int to:g[v])if(to!=p)calc(to,v);
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(root=1;root<=n;root++)if(!sz[root])dfs(root,root),calc(root,root);
	printf("%lld",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

• 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