Submission #1198383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198383		nikolashami	철인 이종 경기 (APIO18_duathlon)	C++20	100 / 100	122 ms	58808 KiB

count_triplets

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

#define pb push_back

const ll N=2e5+4;
vector<ll>g[N],f[N],ob[N],bck[N],comp[N],cur,ljudi;
ll vs[N],up[N],dep[N],col[N],ar[N],sz[N],naj[N],n,m,cr,ans;

void dfst(ll u){
	ljudi.push_back(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){
	sz[u]=1;
	for(ll v:ob[u]){
		if(!(v^p))continue;
		dep[v]=dep[u]+1;
		gd(v,u);
		sz[u]+=sz[v];
	}	
}

void dfsa(ll u,ll p){
	up[u]=N;
	cur.push_back(u);
	for(ll v:ob[u]){
		if(!(v^p))continue;
		dfsa(v,u);
		up[u]=min(up[u],up[v]);
		if(up[v]>=dep[u]){
			ar[u]|=1;
			++cr;
			comp[cr].push_back(u);
			while(cur.back()!=v){
				comp[cr].push_back(cur.back());
				cur.pop_back();
			}
			comp[cr].push_back(v);
			cur.pop_back();
		}
	}
	for(ll v:bck[u])
		up[u]=min(up[u],dep[v]);
}

void dfs3(ll u,ll p){
	sz[u]=1;
	if(u>n)--sz[u];
	for(ll v:f[u]){
		if(!(v^p))continue;
		dfs3(v,u);
		sz[u]+=sz[v];
		if(u<=n)continue;
		ans-=(sz[v])*(sz[v]-1)*(f[u].size()-1);
	}
	if(u<=n)return;
	ans-=(ljudi.size()-sz[u])*(ljudi.size()-sz[u]-1)*(f[u].size()-1);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

   	cin>>n>>m;
   	for(int i=1,u,v;i<=m;++i){
   		cin>>u>>v;
   		g[u].pb(v);
   		g[v].pb(u);
   	}

   	for(int i=1;i<=n;++i){
   		if(vs[i])continue;
   		cur.clear();
   		ljudi.clear();
   		cr=0;
   		dfst(i);
   		ans+=ljudi.size()*(ljudi.size()-1)*(ljudi.size()-2);
   		gd(i,i);
   		dfsa(i,i);
   		for(int j=1;j<=cr;++j){
   			for(ll k:comp[j]){
   				f[k].push_back(n+j);
   				f[n+j].push_back(k);
   			}
   		}
   		dfs3(i,i);
   		for(int j=1;j<=cr;++j){
   			for(ll k:comp[j]){
   				if(f[k].size())f[k].clear();
   				if(f[n+j].size())f[n+j].clear();
   			}
   			comp[j].clear();
   		}
   		for(ll j:ljudi)assert("jbt");
   	}
   	
   	for(int i=1;i<=cr&&0;++i){
   		cout<<"comp#"<<i<<endl;
   		cout<<"[\n";
   		for(auto j:comp[i])cout<<j<<endl;
   		cout<<"]\n";
   	}

   	cout<<ans;
}

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