oj.uz

Submission #982379

# Submission time Handle Problem Language Result Execution time Memory
982379 2024-05-14T07:46:54 Z Jawad_Akbar_JJ Duathlon (APIO18_duathlon) C++17
0 / 100
 106 ms 28008 KB 
#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);

	cout<<lca(14,7)<<endl;

	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 28008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 24728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 24400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -