Submission #568711

#	Time	Username	Problem	Language	Result	Execution time	Memory
568711		inluminas	Duathlon (APIO18_duathlon)	C++17	0 / 100	73 ms	14560 KiB

count_triplets

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const int lmt=1e5+5;
vector<int>adj[lmt];
int vis[lmt],t[lmt],c,sz;

void dfs(int u,int p){
	vis[u]=1,sz++;
	for(int v:adj[u]){
		if(vis[v]) continue;
		t[v]=t[u]+1;
		dfs(v,u);
	}

	for(int v:adj[u]){
		if(v==p) continue;
		if(t[v]<t[u]) c=1;
	}
}

int main(){
	fastio;

	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	ll ans=0;

	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i,0);
		if(sz<3){
			sz=0,c=0;
			continue;
		}
		ll res=sz*(sz-1)*(sz-2);
		res=res/3;
		if(c) res=res*3;
		ans+=res;
		sz=c=0;
	}

	cout<<ans<<endl;
	return 0;
}

• 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