제출 #568705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568705		inluminas	철인 이종 경기 (APIO18_duathlon)	C++17	0 / 100	60 ms	10808 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],c,sz;

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

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);
		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=0,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