Submission #1356870

#TimeUsernameProblemLanguageResultExecution timeMemory
1356870tsengang철인 이종 경기 (APIO18_duathlon)C++20
0 / 100
57 ms12072 KiB
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
struct dsu{
	ll n;
	vector<ll>p,sz;
	dsu(ll _n){
		n = _n;
		p.resize(n+1);
		sz.resize(n+1,1);
		iota(all(p),0);
	}
	ll find(ll x){
		if(x == p[x])return x;
		return p[x] = find(p[x]);
	}
	void merge(ll x,ll y){
		ll a = find(x);
		ll b = find(y);
		if(a == b)return;
		if(sz[b] > sz[a])swap(a,b);
		sz[a]+=sz[b];
		p[b] = a;
		n--;
	}
};
vector<ll>adj[200005];
vector<ll>sz(200005,-1);
ll calc(ll x,ll p){
	sz[x] = 1;
	for(auto y : adj[x]){
		if(y!=p){
			sz[x]+=calc(y,x);
		}
	}
	return sz[x];
}
ll ans = 0;
void dfs(ll x,ll p,ll compsz){
	ll d = compsz - sz[x];
	ll dih = sz[x]-1;
	ans+=dih*d;
	for(auto y : adj[x]){
		if(y!=p){
			dfs(y,x,compsz);
		}
	}
}
int main(){
	ll n,m;
	cin >> n >> m;
	dsu gang(n);
	for(ll i = 0; i < m; i++){
		ll a,b;
		cin >> a >> b;
		ll x = gang.find(a);
		ll y = gang.find(b);
		if(x == y)continue;
		gang.merge(x,y);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(ll i = 1; i <= n; i++){
		if(sz[i] == -1){
			ll comp = calc(i,-1);
			if(comp < 3)continue;
			dfs(i,-1,comp);
		}
	}
	cout << ans*2;
}
#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...