oj.uz

Submission #982380

# Submission time Handle Problem Language Result Execution time Memory
982380 2024-05-14T07:47:33 Z Jawad_Akbar_JJ Duathlon (APIO18_duathlon) C++17
23 / 100
 124 ms 27988 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);

	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 2 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 3 ms 6296 KB Output is correct
8 Correct 3 ms 6236 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 2 ms 6236 KB Output is correct
12 Correct 3 ms 6404 KB Output is correct
13 Correct 2 ms 6232 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct
15 Correct 2 ms 6236 KB Output is correct
16 Correct 2 ms 6236 KB Output is correct
17 Correct 2 ms 6236 KB Output is correct
18 Correct 2 ms 6236 KB Output is correct
19 Correct 2 ms 6236 KB Output is correct
20 Correct 2 ms 6236 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 24504 KB Output is correct
2 Correct 90 ms 24400 KB Output is correct
3 Correct 91 ms 24388 KB Output is correct
4 Correct 95 ms 24484 KB Output is correct
5 Correct 118 ms 24352 KB Output is correct
6 Correct 103 ms 27436 KB Output is correct
7 Correct 103 ms 26488 KB Output is correct
8 Correct 99 ms 26084 KB Output is correct
9 Correct 97 ms 25356 KB Output is correct
10 Correct 87 ms 24400 KB Output is correct
11 Correct 88 ms 24356 KB Output is correct
12 Correct 95 ms 24460 KB Output is correct
13 Correct 89 ms 24360 KB Output is correct
14 Correct 78 ms 24284 KB Output is correct
15 Correct 77 ms 23872 KB Output is correct
16 Correct 49 ms 23036 KB Output is correct
17 Correct 81 ms 24512 KB Output is correct
18 Correct 75 ms 24480 KB Output is correct
19 Correct 70 ms 24500 KB Output is correct
20 Correct 78 ms 24568 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 24400 KB Output is correct
2 Correct 117 ms 24236 KB Output is correct
3 Incorrect 124 ms 24736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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