Submission #568737

#	Time	Username	Problem	Language	Result	Execution time	Memory
568737		inluminas	Duathlon (APIO18_duathlon)	C++17	23 / 100	1102 ms	1048576 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=2e5+10;
vector<ll>adj[lmt];
bool vis[lmt];
ll c[lmt],par[lmt],sz[lmt];
ll ans=0;
map<pair<ll,ll>,ll>z;

ll findpar(ll p){
	if(par[p]==p) return p;
	return par[p]=findpar(par[p]);
} 

void merge(ll u,ll v){
	u=findpar(u),v=findpar(v);
	par[u]=v;
	sz[v]+=sz[u];
	return;
}

void dfs(ll u,ll p){
 	c[u]=vis[u]=1;
 	ll pu=findpar(u);
 	for(ll v:adj[u]){
 		if(v==p) continue; 
 		dfs(v,u);
 		c[u]+=c[v];
 		z[{u,v}]=c[v];
 		z[{v,u}]=sz[pu]-c[v];
 	}
}

int main(){
	fastio;

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

	for(ll i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i,0);
	}

	for(ll i=1;i<=n;i++){
		ll p=findpar(i);
		for(ll v:adj[i]){
			ll val=z[{i,v}];
			ans+=(val*(sz[p]-val-1));
		}
	}

	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10