Submission #982380

#	Time	Username	Problem	Language	Result	Execution time	Memory
982380		Jawad_Akbar_JJ	Duathlon (APIO18_duathlon)	C++17	23 / 100	124 ms	27988 KiB

count_triplets

#include <iostream>
#include <vector>
 
using namespace std;
#define int long long
const int N = 1e5 + 10,lg = 18;
vector<int> nei[N];
int par[N][lg + 1],Seen[N],cur = 10,ch[N];
int Par[N], hei[N];

void dfs(int u,int p = 0){
	hei[u] = hei[p] + 1;

	par[u][0] = p;

	for (int i=1;i<=lg;i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for (int i : nei[u])
		if (i != p)
			dfs(i,u);
}

int root(int v){
	if (Par[v] == 0)
		return v;
	Par[v] = root(Par[v]);
	return Par[v];
}

void lift(int & v,int d){
	for (int i=0;i<=lg;i++)
		if ((1<<i) & d)
			v = par[v][i];
}

int lca(int u,int v){
	if (hei[u] > hei[v])
		swap(u,v);
	
	lift(v,hei[v] - hei[u]);

	if (u == v)
		return u;
	for (int i=lg;i>=0;i--)
		if (par[u][i] != par[v][i]){
			cout<<u<<" "<<v<<" "<<i<<" ";
			u = par[u][i], v = par[v][i];
			cout<<u<<" "<<v<<endl;
		}
	return par[u][0];
}












void dfs31(int u,int p = -1){
	Seen[u] = true;
	ch[u] = 1;
	for (int i : nei[u])
		if (i != p)
			dfs31(i,u),ch[u] += ch[i];
}
int ans = 0;
void dfs32(int u,int rt,int p = -1){
	int S = ch[rt] - ch[u];
	for (int i : nei[u])
		if (i != p)
			ans += ch[i] * S,S += ch[i];
	for (int i : nei[u])
		if (i != p)
			dfs32(i,rt,u);
}
 
void sub45(int n){
	for (int i=1;i<=n;i++)
		if (!Seen[i]){
			dfs31(i);
			dfs32(i,i);
		}
}





signed main(){
	int n,m;
	cin>>n>>m;
 
	vector<pair<int,int>> vec;;

	for (int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		int u = root(a);
		int v = root(b);
		if (u == v){
			vec.push_back({a,b});
			continue;
		}

		Par[u] = v;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	for (int i=1;i<=n;i++)
		if (hei[i] == 0)
			dfs(i);

	sub45(n);

	ans = ans * 2;

	for (auto [a,b] : vec){
		int l = lca(a,b);
		int d = hei[a] + hei[b] - 2 * hei[l];
		for (int i=1;i<=d;i++)
			ans -= (i-1) * (d - i) * 2;
		ans += d * (d - 1) * (d - 2);
	}
	cout<<ans<<'\n';


}

/*

16 16
1 2
1 3
3 4
3 5
3 6
5 7
5 8
5 9
2 10
2 11
11 12
11 13
13 15
13 16
13 14
14 7



*/

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