Submission #1043279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043279		vjudge1	Duathlon (APIO18_duathlon)	C++17	23 / 100	1054 ms	1048576 KiB

count_triplets

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

#define int long long
int const N=2e5+5;
int const mod=1e9+7;

vector<int> adj[N];
vector<int> mem[N];
int sz[N];
int c=0;
void dfs(int node,int par){
	mem[c].push_back(node);
	for(int i:adj[node])
		if(i!=par){
			dfs(i,node);
			sz[node]+=sz[i];
		}
	sz[node]++;
}

signed main(){
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < m; ++i)
	{
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int ans=0;
	for (int i = 1; i <=n; ++i)
		if(sz[i]==0){
			dfs(i,0);
			int cc=sz[i];
			ans+=cc*(cc-1)*(cc-1);
			ans+=cc*cc;
			for(int j:mem[c]){
				ans-=sz[j]*sz[j];
				ans-=(cc-sz[j])*(cc-sz[j]);
			}
			c++;
		}
	cout<<ans<<endl;
	return 0;
}

• 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