Submission #109653

#	Time	Username	Problem	Language	Result	Execution time	Memory
109653		user202729	Duathlon (APIO18_duathlon)	C++17	100 / 100	277 ms	31560 KiB

count_triplets

// https://oj.uz/problem/view/APIO18_duathlon
#include<iostream>
#include<vector>
#include<cassert>

std::vector<std::vector<int>> adjl;

int nnode;

int lastnum=0;
std::vector<int> dnum,dlow;
std::vector<int> stk;

// adjlist for circle-square-tree
// node with index < nnode are real
std::vector<std::vector<int>> cst_adjl;

int64_t ans;
void dfs(int node,int par){
	assert(dnum[node]==0);
	dnum[node]=dlow[node]=++lastnum;
	stk.push_back(node);
	for(int ad:adjl[node]){
		if(ad==par)continue;
		if(dnum[ad])
			dlow[node]=std::min(dlow[node],dnum[ad]);
		else{ // ad is a child of node
			dfs(ad,node);
			if(dlow[ad]>=dnum[node]){
				// it creates a new biconnected component
				auto iter=--stk.end();
				while(*iter!=ad)--iter;

				std::vector<int> v;
				v.reserve(stk.end()-iter+1);
				v.assign(iter,stk.end());
				v.push_back(node);

				int newnode=(int)cst_adjl.size();
				assert(newnode>=nnode);
				for(int x:v)
					cst_adjl[x].push_back(newnode);
				cst_adjl.push_back(std::move(v));

				stk.erase(iter,stk.end());
			}else{
				dlow[node]=std::min(dlow[node],dlow[ad]);
			}
		}
	}
}

std::vector<int> cst_par,
	cst_stsize /* only includes real nodes */;
void dfs2(int node){
	int& cst_stsize_node=cst_stsize[node];
	assert(cst_stsize_node==0);
	cst_stsize_node=node<nnode;
	for(int adj:cst_adjl[node])if(adj!=cst_par[node]){
		cst_par[adj]=node;
		dfs2(adj);
		cst_stsize_node+=cst_stsize[adj];
	}
	assert(cst_stsize_node>0);
}

std::vector<int64_t> ssqr;

int64_t sqr(int x){return (int64_t)x*x;}

int ccsize; // size of currently considering connected component, in real nodes
void dfs3(int node){
	if(node<nnode){
		// consider c == node. how many of (s,t) pairs are over-counted?
		for(int d:cst_adjl[node]){
			// assume s and t are "to the direction of d" from c
			assert(d>=nnode&&cst_adjl[d].size()>1);
			int64_t& ssqr_d=ssqr[d-nnode];
			if(ssqr_d==0){
				// compute ssqr_d first
				assert(d!=cst_par[node]);
				for(int x:cst_adjl[d])
					if(cst_par[d]==x)
						ssqr_d+=sqr(ccsize-cst_stsize[d]);
					else
						ssqr_d+=sqr(cst_stsize[x]);
				assert(ssqr_d!=0);

				ans-=ssqr_d;
				ans+=sqr(ccsize-cst_stsize[d]);
			}else{
				assert(d==cst_par[node]);

				ans-=ssqr_d;
				ans+=sqr(cst_stsize[node]);
			}
		}
	}
	for(int adj:cst_adjl[node])if(adj!=cst_par[node]){
		dfs3(adj);
	}
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int nedge;std::cin>>nnode>>nedge;
	adjl.resize(nnode);
	for(int i=nedge;i-->0;){
		int u,v;std::cin>>u>>v;
		--u;--v;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}

	dnum.resize(nnode);
	dlow.resize(nnode);
	ans=0;
	cst_adjl.resize(nnode);
	std::vector<int> fnodes; // each connected component has exactly one fnode
	for(int node=0;node<nnode;++node)if(dnum[node]==0){
		fnodes.push_back(node);
		assert(stk.empty());
		dfs(node,-1);
		assert(stk.size()==1&&stk[0]==node);
		stk.clear();
	}

	cst_par.assign(cst_adjl.size(),-1);
	cst_stsize.resize(cst_adjl.size());
	ssqr.resize(cst_adjl.size()-nnode);
	for(int x:fnodes){
		assert(x<nnode);
		dfs2(x);

		ccsize=cst_stsize[x];
		ans+=ccsize // for each way to choose vertex c
			*(ccsize-1LL)*(ccsize-1); // there are at most % ways to choose s and t
		// (allow them to overlap but not the same as c)
		dfs3(x);
	}

	std::cout<<ans<<'\n';
}

/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

5 6
1 2 1 3 2 3 2 4 2 5 4 5
*/

• 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