Submission #568720

#	Time	Username	Problem	Language	Result	Execution time	Memory
568720		inluminas	Duathlon (APIO18_duathlon)	C++17	8 / 100	97 ms	12496 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 ll lmt=1e5+5;
vector<ll>adj[lmt];
ll vis[lmt],c,sz;

void dfs(ll u,ll p){
	vis[u]=1,sz++;
	for(ll v:adj[u]){
		if(v!=p && vis[v]==1){
			c=1;
		}
		if(vis[v]) continue;
		dfs(v,u);
	}
	vis[u]=2;
}

int main(){
	fastio;

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

	ll ans=0;

	for(ll 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: 8 / 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