Submission #103701

#	Time	Username	Problem	Language	Result	Execution time	Memory
103701		autumn_eel	Duathlon (APIO18_duathlon)	C++14	0 / 100	147 ms	12024 KiB

count_triplets

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int n,m;
vector<int>E[200000];
int sz[200000];
bool used[200000];
ll ans=0;

void dfs(int v,int p){
	used[v]=true;
	int s=n-1;
	sz[v]=1;
	for(int u:E[v]){
		if(used[u])continue;
		dfs(u,v);
		sz[v]+=sz[u];
		s-=sz[u];
		ans+=sz[u]*(ll)(n-sz[u]-1);
	}
	ans+=s*(ll)(n-s-1);
}
int main(){
	scanf("%d%d",&n,&m);
	assert(m<=n-1);
	rep(i,m){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	rep(i,n){
		if(!used[i]){
			dfs(i,-1);
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:26: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:29:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b;scanf("%d%d",&a,&b);a--;b--;
           ~~~~~^~~~~~~~~~~~~~

• 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