Submission #1196927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196927		nouka28	Duathlon (APIO18_duathlon)	C++20	0 / 100	165 ms	95300 KiB

count_triplets

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

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

struct LowLink{
	vector<vector<int>> g;
	int n;
	vector<int> ord,low;
	vector<vector<int>> son,back_edge;
	vector<int> tps;

	LowLink(vector<vector<int>> g_){
		g=g_,n=(int)g.size();
		ord.assign(n,-1);low.assign(n,-1);
		son.assign(n,vector<int>());back_edge.assign(n,vector<int>());
		tps.clear();
		int t=0;
		stack<pair<int,int>> st;
		vector<bool> conduct(n,false);
		for(int i=0;i<n;i++){
			if(conduct[i])continue;
			st.push({-1,i});
			while(!st.empty()){
				auto[pre,now]=st.top();st.pop();
				conduct[now]=true;
				if(ord[now]!=-1){
					if(ord[pre]<ord[now])continue;
					low[pre]=min(low[pre],ord[now]);
					back_edge[pre].push_back(now);
					continue;
				}
				if(pre!=-1){
					son[pre].push_back(now);
				}
				tps.push_back(now);
				ord[now]=low[now]=t;t++;
				for(int nex:g[now]){
					if(nex==pre)continue;
					st.push({now,nex});
				}
			}
		}
		for(int i=(int)tps.size()-1;i>=0;i--){
			for(int e:son[tps[i]]){
				low[tps[i]]=min(low[tps[i]],low[e]);
			}
		}
	}
	
	vector<pair<int,int>> bridges(){
		vector<pair<int,int>> res;
		for(int i=0;i<n;i++){
			for(int e:son[i]){
				if(low[e]>ord[i]){
					res.push_back({min(i,e),max(i,e)});
				}
			}
		}
		return res;
	}

	//tecc,tecc_idx,tecc_tree
	tuple<vector<vector<int>>,vector<int>,vector<vector<int>>> TwoEdgeConnectedComponentDecomposition(){
		vector<vector<int>> tecc,tecc_tree;
		vector<int> tecc_idx(n,-1);
		stack<pair<int,int>> sub_roots;
		int idx=0;
		vector<bool> conduct(n,false);
		for(int i=0;i<n;i++){
			if(conduct[i])continue;
			sub_roots.push({-1,i});
			while(!sub_roots.empty()){
				stack<pair<int,int>> st;st.push(sub_roots.top());sub_roots.pop();
				tecc.push_back(vector<int>());tecc_tree.push_back(vector<int>());
				while(!st.empty()){
					auto[pre,now]=st.top();st.pop();
					conduct[now]=true;
					tecc[idx].push_back(now);
					tecc_idx[now]=idx;
					if(pre!=-1&&idx!=tecc_idx[pre]){
						tecc_tree[idx].push_back(tecc_idx[pre]);
						tecc_tree[tecc_idx[pre]].push_back(idx);
					}
					for(auto e:son[now]){
						if(low[e]>ord[now]){
							sub_roots.push({now,e});
						}else{
							st.push({now,e});
						}
					}
				}
				idx++;
			}
		}
		return {tecc,tecc_idx,tecc_tree};
	}

	//bce,bcv,is_ap
	tuple<vector<vector<pair<int,int>>>,vector<vector<int>>,vector<bool>> BiconnectedComponentDecomposition(){
		vector<vector<pair<int,int>>> bce;
		vector<vector<int>> bcv;
		vector<bool> is_ap(n,false);
		stack<pair<int,int>> sub_roots;
		vector<bool> conduct(n,false);
		int idx=0;
		for(int i=0;i<n;i++){
			if(conduct[i])continue;
			sub_roots.push({-1,i});
			while(!sub_roots.empty()){
				stack<pair<int,int>> st;st.push(sub_roots.top());sub_roots.pop();
				bce.push_back(vector<pair<int,int>>());bcv.push_back(vector<int>());
				if(st.top().first!=-1){
					bcv[idx].push_back(st.top().first);
				}
				while(!st.empty()){
					auto[pre,now]=st.top();st.pop();
					conduct[now]=true;
					if(pre!=-1)bce[idx].push_back({pre,now});
					bcv[idx].push_back(now);
					if(now==i){
						if((int)son[now].size()>1){
							for(int e:son[now]){
								is_ap[now]=true;
								sub_roots.push({now,e});
							}
							bce.pop_back();bcv.pop_back();idx--;
						}else{
							for(int e:son[now]){
								st.push({now,e});
							}
						}
					}else{
						for(int e:son[now]){
							if(low[e]>=ord[now]){
								is_ap[now]=true;
								sub_roots.push({now,e});
							}else{
								st.push({now,e});
							}
						}
					}
					if(now==i&&(int)son[now].size()<=1){
						for(int back:back_edge[now]){
							bce[idx].push_back({now,back});
						}
					}
				}
				idx++;
			}
		}
		return {bce,bcv,is_ap};
	}

	//bc,bc_idx,bc_tree,num_ap,bce,bcv,is_ap
	struct block_cut_tree_result{
		vector<vector<int>> bc;
		vector<int> bc_idx;
		vector<vector<int>> bc_tree;
		int num_ap;
		vector<vector<pair<int,int>>> bce;
		vector<vector<int>> bcv;
		vector<bool> is_ap;
	};
	
	block_cut_tree_result block_cut_tree(){
		auto[bce,bcv,is_ap]=BiconnectedComponentDecomposition();
		int num_ap=0;for(bool f:is_ap)num_ap+=f;
		vector<vector<int>> bc(num_ap+(int)bcv.size(),vector<int>());
		vector<int> bc_idx(n,-1);
		vector<vector<int>> bc_tree(num_ap+(int)bcv.size(),vector<int>());
		int idx=0;
		for(int i=0;i<n;i++){
			if(is_ap[i]){
				bc[idx].push_back(i);
				bc_idx[i]=idx;
				idx++;
			}
		}
		for(vector<int> bcv_i:bcv){
			for(int v:bcv_i){
				if(is_ap[v]){
					bc_tree[idx].push_back(bc_idx[v]);
					bc_tree[bc_idx[v]].push_back(idx);
				}else{
					bc[idx].push_back(v);
					bc_idx[v]=idx;
				}
			}
			idx++;
		}
		return {bc,bc_idx,bc_tree,num_ap,bce,bcv,is_ap};
	}
	
};


signed main(){
	int N,M;cin>>N>>M;
	vector<vector<int>> g(N);
	rep(i,M){
		int u,v;cin>>u>>v;u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	LowLink lowlink(g);

	auto ret=lowlink.block_cut_tree();
	int ans=0;

	auto dfs=[&](auto dfs,int p,int prev=-1)->int {
		int nsz=ret.bc[p].size();
		int sz_sum=nsz;
		if(p<ret.num_ap){
			int sm1=0,sm2=0;
			for(auto&&e:ret.bc_tree[p]){
				if(e==prev)continue;
				int t=dfs(dfs,e,p);
				sz_sum+=t;
				sm1+=t;
				sm2+=t*t;
			}
			sm1+=(N-sz_sum),sm2+=(N-sz_sum)*(N-sz_sum);
			ans+=sm1*sm1-sm2;
			for(auto&&e:ret.bc_tree[p]){
				int t=ret.bc[e].size();
				ans+=t*(t-1);
			}
		}else{
			ans+=nsz*(nsz-1)*(nsz-2);
			int sm1=0,sm2=0;
			for(auto&&e:ret.bc_tree[p]){
				if(e==prev)continue;
				int t=dfs(dfs,e,p);
				sz_sum+=t;
				sm1+=t;
				sm2+=t*t;
			}
			sm1+=(N-sz_sum),sm2+=(N-sz_sum)*(N-sz_sum);
			ans+=nsz*(sm1*sm1-sm2);
			ans+=nsz*(nsz-1)*sm1*2;
		}

		return sz_sum;
	};

	dfs(dfs,0);

	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