Submission #1197894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197894		nikolashami	Duathlon (APIO18_duathlon)	C++20	0 / 100	83 ms	33092 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

#define pb push_back

const ll N=1e5+2;
vector<ll>g[N],f[N],ob[N],bck[N];
ll vs[N],up[N],dep[N],par[N],col[N],ar[N],w[N],sz[N],ar2[N],cr,ans;

void dfst(ll u){
	vs[u]=1;
	for(ll v:g[u]){
		if(vs[v]){
			bck[u].pb(v);
			bck[v].pb(u);
		}else{
			ob[u].pb(v);
			ob[v].pb(u);
			dfst(v);
		}
	}
}

void gd(ll u,ll p){
	par[u]=p;
	for(ll v:ob[u]){
		if(!(v^p))continue;
		dep[v]=dep[u]+1;
		gd(v,u);
	}	
}

void dfsa(ll u,ll p){
	up[u]=N;
	ll mx=0;
	for(ll v:ob[u]){
		if(!(v^p))continue;
		dfsa(v,u);
		up[u]=min(up[u],up[v]);
		mx=max(mx,up[v]);
	}
	if(mx>=dep[u]&&ob[u].size()>1)ar[u]=1;
	for(ll v:bck[u])
		up[u]=min(up[u],dep[v]);
}

ll cnt;
void dfsc(ll u){
	vs[u]=1;
	col[u]=cr;
	++cnt;
	for(ll v:g[u]){
		if(vs[v]||ar[v])continue;
		dfsc(v);
	}
}

void get(ll u,ll p){
	if(u==1)dep[u]=w[u];
	sz[u]=w[u];
	par[u]=p;
	for(ll v:f[u]){
		if(!(v^p))continue;
		dep[v]=dep[u]+w[v];
		get(v,u);
		sz[u]+=sz[v];
	}
}

void dfs(ll u,ll p){
	ll s=0;
	for(ll v:f[u]){
		if(!(v^p))continue;
		s+=sz[v];
	}
	ll tmp=ans;
	ans+=(w[u]-1)*dep[par[u]]*2*w[u];
	for(ll v:f[u]){
		if(!(v^p))continue;
		ans+=(w[u]-1)*sz[v]*2*w[u];
		ans+=(dep[par[u]])*sz[v]*2*w[u];
		ans+=sz[v]*(s-sz[v])*2*w[u];
		ans+=w[v]*(w[v]-1)*w[u];
	}
	ans+=(w[u]-1)*(w[u]-2)*w[u];
	ans+=(w[par[u]])*(w[par[u]]-1)*w[u];
	ll delta=ans-tmp;
	//cout<<u<<' '<<delta<<endl;
	for(ll v:f[u]){
		if(v^p)dfs(v,u);
	}
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n,m;
   	cin>>n>>m;
   	for(int i=1,u,v;i<=m;++i){
   		cin>>u>>v;
   		g[u].pb(v);
   		g[v].pb(u);
   	}

   	dfst(1);
   	gd(1,0);
   	dfsa(1,0);

   	fill(vs,vs+n+1,0);
   	for(int i=1;i<=n;++i){
   		if(!ar[i])continue;
   		for(int j:g[i]){
   			if(!vs[j]&&!ar[j]){
   				++cr;
   				cnt=0;
   				dfsc(j);
   				cr-=!cnt;
   			}
   		}
   	}

   	for(int i=1;i<=n;++i){
   		if(ar[i])col[i]=++cr;
   		ar2[cr]=1;
   	}

   	for(int i=1;i<=n;++i)
   		++w[col[i]];

   	set<ll>ss;
   	for(int i=1;i<=n;++i){
   		if(!ar[i])continue;
   		ss.clear();
   		for(int j:g[i]){
   			if(ss.find(col[j])!=ss.end())continue;
   			ss.insert(col[j]);
   			f[col[i]].pb(col[j]);
   			if(!ar[j])f[col[j]].pb(col[i]);
   		}
   	}

   	get(1,0);
   	dfs(1,0);

   	bool ok=0;
   	for(int i=1;i<=n;++i)ok|=ar[i];

   	if(!ok)ans=n*(n-1)*(n-2);
   	cout<<ans<<endl;
}

• 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