oj.uz

Submission #983011

# Submission time Handle Problem Language Result Execution time Memory
983011 2024-05-15T06:57:54 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 38 ms 15964 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, i, j, x, y, ans, sz[200001], rt[200001];
bool u[200001];
vector<int> g[200001], v;

void dfs(int x, int r) {
	sz[x] = 1;
	u[x] = 1;
	rt[x] = r;
	for (auto y : g[x]) {
		if (u[y]) continue;
		dfs(y, r);
		sz[x] += sz[y];
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif
	cin >> n >> m;
	while (m--) {
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	v.push_back(1);
	dfs(1, 1);
	for (i = 1; i <= n; i++) {
		if (!u[i]) {
			v.push_back(i);
			dfs(i, i);
		}
	}
	for (int i : v) {
		ans -= (sz[i]) * (sz[i] - 1); // + (x, x)
	}
	for (i = 1; i <= n; i++) {
		//cout << i << " " << rt[i] << " " << sz[i] << " " << sz[rt[i]] << " " << sz[rt[i]] - sz[i] << "\n";
		ans += 2 * (sz[i] - 1) * (sz[rt[i]] - sz[i]);
		ans += 2 * (sz[rt[i]] - sz[i]); // - (x, x)
	}
	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 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 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 15964 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 2 ms 5208 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 4 ms 5032 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 3 ms 5064 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 2 ms 5208 KB Output is correct
14 Correct 3 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 3 ms 5008 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10328 KB Output is correct
2 Correct 30 ms 11752 KB Output is correct
3 Correct 31 ms 11584 KB Output is correct
4 Correct 29 ms 11600 KB Output is correct
5 Correct 31 ms 11600 KB Output is correct
6 Correct 36 ms 14428 KB Output is correct
7 Correct 36 ms 13904 KB Output is correct
8 Correct 33 ms 13296 KB Output is correct
9 Correct 32 ms 12636 KB Output is correct
10 Correct 31 ms 11708 KB Output is correct
11 Correct 30 ms 11612 KB Output is correct
12 Correct 29 ms 11604 KB Output is correct
13 Correct 32 ms 11596 KB Output is correct
14 Correct 26 ms 11612 KB Output is correct
15 Correct 33 ms 11348 KB Output is correct
16 Correct 17 ms 10456 KB Output is correct
17 Correct 21 ms 11984 KB Output is correct
18 Correct 22 ms 12008 KB Output is correct
19 Correct 23 ms 11828 KB Output is correct
20 Correct 23 ms 11840 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10324 KB Output is correct
2 Correct 30 ms 11600 KB Output is correct
3 Incorrect 35 ms 12180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 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 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -