제출 #1361693

#제출 시각아이디문제언어결과실행 시간메모리
1361693khangai11철인 이종 경기 (APIO18_duathlon)C++20
0 / 100
1115 ms1114112 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<ll>> g;
vector<ll> st;
pair<pair<ll,ll>,ll> dfs(ll i,ll p){
	pair<pair<ll,ll>,ll> pr;
	st[i]=1;
	pr={{1,0},0};
	for(auto z:g[i]){
		if(z==p){
			continue;
		}
		pair<pair<ll,ll>,ll> p1;
		p1=dfs(z,i);
		pr.second+=p1.second;
		pr.second+=p1.first.first*(pr.first.first-1);
		pr.second+=p1.first.second*pr.first.first;
		pr.second+=p1.first.first*pr.first.second;
		pr.first.second+=p1.first.second;
		pr.first.second+=p1.first.first;
		pr.first.first+=p1.first.first;
	}
	return pr;
}
void solve(){
	ll n,m;
	cin>>n>>m;
	g.resize(n+1);
	st.resize(n+1,0);
	for(ll a=0;a<m;a++){
		ll u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	ll D=0;
	for(ll a=1;a<=n;a++){
		if(st[a]==1){
			continue;
		}
		D+=dfs(a,0).second;
	}
	cout<<D*2<<endl;
}
signed main(){
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
	for(ll a=0;a<t;a++){
		solve();
	}
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…