oj.uz

Submission #405467

# Submission time Handle Problem Language Result Execution time Memory
405467 2021-05-16T12:42:51 Z saleh Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;


const int MAXN = 100 * 1000 + 23;















int n, m, sz[MAXN], save, ans;
vector<int> g[MAXN];
bitset<MAXN> mark;

int ent(int x) { return x * (x - 1); }
int gs(int v, int p) {
	mark[v] = true;
	for (auto i : g[v]) if (i != p) sz[v] += gs(i, v);
	return ++sz[v];
}
void dfs(int v, int p) {
	for (auto i : g[v]) if (i != p) dfs(i, v);
	for (auto i : g[v]) if (i != p) ans -= ent(save - sz[i]);
	if (~p) ans -= ent(sz[v]);
}


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v), g[v].push_back(u);
	}
	for (int i = 0; i < n; i++) if (!mark[i]) {
		save = gs(i, -1);
		ans += save * (save - 1) * (save - 2);
		dfs(i, -1);
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1111 ms 335020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2684 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2684 KB Output is correct
6 Correct 3 ms 2680 KB Output is correct
7 Correct 3 ms 2684 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 3 ms 2680 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2676 KB Output is correct
16 Correct 3 ms 2676 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2680 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7516 KB Output is correct
2 Correct 66 ms 7492 KB Output is correct
3 Correct 60 ms 7436 KB Output is correct
4 Correct 59 ms 7328 KB Output is correct
5 Correct 57 ms 7356 KB Output is correct
6 Correct 73 ms 9364 KB Output is correct
7 Correct 83 ms 8992 KB Output is correct
8 Correct 75 ms 8620 KB Output is correct
9 Correct 69 ms 8128 KB Output is correct
10 Correct 67 ms 7440 KB Output is correct
11 Correct 75 ms 7280 KB Output is correct
12 Correct 61 ms 7204 KB Output is correct
13 Correct 71 ms 7312 KB Output is correct
14 Correct 50 ms 7072 KB Output is correct
15 Correct 48 ms 6824 KB Output is correct
16 Correct 28 ms 5956 KB Output is correct
17 Correct 39 ms 7496 KB Output is correct
18 Correct 45 ms 7440 KB Output is correct
19 Correct 40 ms 7468 KB Output is correct
20 Correct 45 ms 7492 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Runtime error 745 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7492 KB Output is correct
2 Correct 61 ms 7208 KB Output is correct
3 Runtime error 978 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -