Submission #1013994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013994		pcc	Duathlon (APIO18_duathlon)	C++17	100 / 100	79 ms	33740 KiB

count_triplets

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

#define ll long long
const int mxn = 1e5+10;
vector<int> paths[mxn],tree[mxn*2];
int N,M;
bitset<mxn> vis;
ll ans = 0;

namespace TARJAN{
	int idx[mxn],low[mxn],gcnt,cnt;
	vector<int> st,gid[mxn];

	void dfs(int now,int par){
		st.push_back(now);
		low[now] = idx[now] = ++cnt;
		for(auto nxt:paths[now]){
			if(idx[nxt]){
				low[now] = min(low[now],idx[nxt]);
			}
			else{
				dfs(nxt,now);
				low[now] = min(low[now],low[nxt]);
				if(low[nxt] == idx[now]){
					gcnt++;
					int id = st.back();
					do{
						assert(!st.empty());
						id = st.back();st.pop_back();
						gid[id].push_back(gcnt);
						tree[gcnt+N].push_back(id);
						tree[id].push_back(gcnt+N);
					}while(id != nxt);
					gid[now].push_back(gcnt);
					tree[gcnt+N].push_back(now);
					tree[now].push_back(gcnt+N);
				}
			}

		}
		return;
	}

	void GO(){
		for(int i = 1;i<=N;i++){
			if(gid[i].empty())dfs(i,i);
		}
		return;
	}
}

namespace DP{
	int dp[mxn*2];
	bitset<mxn*2> vis;
	void dfs1(int now,int fa){
		if(now<=N)dp[now] = 1;
		else dp[now] = 0;
		vis[now] = true;
		for(auto nxt:tree[now]){
			if(nxt == fa)continue;
			dfs1(nxt,now);
			dp[now] += dp[nxt];
		}
		return;
	}
	void dfs2(int now,int fa,int sz){
		for(auto nxt:tree[now]){
			if(nxt == fa)continue;
			dfs2(nxt,now,sz);
		}
		if(now>N){
			ll tans = 0,sum = 0;
			for(auto nxt:tree[now]){
				if(nxt == fa)continue;
				tans += sum*dp[nxt]*2;
				sum += dp[nxt];
			}
			ll tmp = sz-dp[now];
			tans += sum*tmp*2;
			sum += tmp;
			ans += tans*((int)tree[now].size()-2);
			return;
		}
		else{
			ll sum = 0;
			for(auto nxt:tree[now]){
				if(nxt == fa)continue;
				ans += sum*dp[nxt]*2;
				sum += dp[nxt];
			}
			ll tmp = sz-dp[now];
			ans += sum*tmp*2;
			return;
		}

	}
	void GO(){
		for(int i = 1;i<=N;i++){
			if(vis[i])continue;
			dfs1(i,i);
			dfs2(i,i,dp[i]);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		int a,b;
		cin>>a>>b;
		paths[a].push_back(b);
		paths[b].push_back(a);
	}
	TARJAN::GO();
	DP::GO();
	cout<<ans<<'\n';
	return 0;
}

• 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