Submission #1013954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013954		pcc	Duathlon (APIO18_duathlon)	C++17	10 / 100	1057 ms	1048576 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int mxn = 1e5+10;
vector<int> tree[mxn];
int N,M;
bitset<mxn> vis;
int dp[mxn];
ll ans = 0;

void dfs1(int now,int fa){
	dp[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == fa)continue;
		dfs1(nxt,now);
		dp[now] += dp[nxt];
	}
	return;
}
void dfs2(int now,int fa,int sz){
	ll sum = 0;
	for(auto nxt:tree[now]){
		if(nxt == fa)continue;
		ans += sum*dp[nxt]*2;
		sum += dp[nxt];
	}
	ll ts = sz-dp[now];
	ans += sum*ts*2;
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=N;i++){
		if(vis[i])continue;
		dfs1(i,i);
		dfs2(i,i,dp[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10