Submission #1361709

#TimeUsernameProblemLanguageResultExecution timeMemory
1361709khangai11Duathlon (APIO18_duathlon)C++20
23 / 100
1026 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;
	ll a1=0,a2=0,a3=0,a4=0,a5=0,a6=0;
	for(auto z:g[i]){
		if(z==p){
			continue;
		}
		pair<pair<ll,ll>,ll> p1;
		p1=dfs(z,i);
		a1+=p1.first.first;
		a2+=p1.first.second;
		a3+=p1.second;
		a4+=p1.first.first*p1.first.second;
		a5+=p1.first.first*p1.first.first;
	}
	pr.second=a3+a2+a1*a2-a4+(a1*a1-a5)/2;
	pr.first.second=a1+a2;
	pr.first.first=1+a1;
	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();
	}
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...