Submission #103703

#	Time	Username	Problem	Language	Result	Execution time	Memory
103703		autumn_eel	Duathlon (APIO18_duathlon)	C++14	23 / 100	151 ms	12104 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 used1[200000],used2[200000];
ll ans=0;
int cnt=0;

void dfs1(int v){
	cnt++;
	used1[v]=true;
	for(int u:E[v]){
		if(used1[u])continue;
		dfs1(u);
	}
}
void dfs2(int v,int p){
	used2[v]=true;
	int s=cnt-1;
	sz[v]=1;
	for(int u:E[v]){
		if(used2[u])continue;
		dfs2(u,v);
		sz[v]+=sz[u];
		s-=sz[u];
		ans+=sz[u]*(ll)(cnt-sz[u]-1);
	}
	ans+=s*(ll)(cnt-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(!used1[i]){
			cnt=0;
			dfs1(i);
			dfs2(i,-1);
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:35: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:38: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: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10