oj.uz

Submission #111867

# Submission time Handle Problem Language Result Execution time Memory
111867 2019-05-16T13:02:31 Z square1001 Duathlon (APIO18_duathlon) C++14
31 / 100
 204 ms 19320 KB 
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int> > G(N);
	for(int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> C(N), P(N), R(N);
	vector<bool> vis(N), cycle(N);
	int total = 0, comp = 0;
	function<void(int, int, int)> dfs = [&](int pos, int pre, int root) {
		P[pos] = pre;
		C[pos] = 1;
		R[pos] = root;
		vis[pos] = true;
		++comp;
		for(int i : G[pos]) {
			++total;
			if(vis[i]) continue;
			dfs(i, pos, root);
			C[pos] += C[i];
		}
	};
	for(int i = 0; i < N; ++i) {
		if(C[i] == 0) {
			total = 0, comp = 0;
			dfs(i, -1, i);
			if(comp * 2 == total) {
				cycle[i] = true;
			}
		}
	}
	long long ans = 0;
	for(int i = 0; i < N; ++i) {
		int rem = C[R[i]] - 1;
		long long sum = 1LL * rem * (rem - 1);
		if(!cycle[R[i]]) {
			for(int j : G[i]) {
				if(j == P[i]) continue;
				rem -= C[j];
				sum -= 1LL * C[j] * (C[j] - 1);
			}
			sum -= 1LL * rem * (rem - 1);
		}
		ans += sum;
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18128 KB Output is correct
2 Correct 145 ms 19320 KB Output is correct
3 Correct 173 ms 13764 KB Output is correct
4 Correct 164 ms 16508 KB Output is correct
5 Correct 138 ms 12040 KB Output is correct
6 Correct 130 ms 11896 KB Output is correct
7 Correct 169 ms 10428 KB Output is correct
8 Correct 196 ms 11324 KB Output is correct
9 Correct 163 ms 9384 KB Output is correct
10 Correct 204 ms 10488 KB Output is correct
11 Correct 131 ms 8056 KB Output is correct
12 Correct 141 ms 7908 KB Output is correct
13 Correct 130 ms 7800 KB Output is correct
14 Correct 122 ms 7680 KB Output is correct
15 Correct 116 ms 7160 KB Output is correct
16 Correct 73 ms 7032 KB Output is correct
17 Correct 8 ms 3840 KB Output is correct
18 Correct 7 ms 3968 KB Output is correct
19 Correct 7 ms 3968 KB Output is correct
20 Correct 7 ms 3840 KB Output is correct
21 Correct 7 ms 3840 KB Output is correct
22 Correct 7 ms 3840 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 7416 KB Output is correct
2 Correct 140 ms 7496 KB Output is correct
3 Correct 124 ms 7380 KB Output is correct
4 Correct 151 ms 7360 KB Output is correct
5 Correct 159 ms 7452 KB Output is correct
6 Correct 141 ms 13364 KB Output is correct
7 Correct 164 ms 11356 KB Output is correct
8 Correct 166 ms 10168 KB Output is correct
9 Correct 152 ms 9196 KB Output is correct
10 Correct 148 ms 7368 KB Output is correct
11 Correct 165 ms 7372 KB Output is correct
12 Correct 144 ms 7416 KB Output is correct
13 Correct 148 ms 7288 KB Output is correct
14 Correct 151 ms 7332 KB Output is correct
15 Correct 124 ms 7160 KB Output is correct
16 Correct 79 ms 6520 KB Output is correct
17 Correct 126 ms 7664 KB Output is correct
18 Correct 126 ms 7644 KB Output is correct
19 Correct 135 ms 7616 KB Output is correct
20 Correct 125 ms 7608 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 7260 KB Output is correct
2 Correct 184 ms 7124 KB Output is correct
3 Incorrect 197 ms 7272 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 256 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 256 KB Output isn't correct
2 Halted 0 ms 0 KB -