oj.uz

Submission #973894

# Submission time Handle Problem Language Result Execution time Memory
973894 2024-05-02T12:23:04 Z dubabuba Duathlon (APIO18_duathlon) C++14
23 / 100
 95 ms 22352 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2e5 + 10;
vector<int> adj[mxn];
vector<pii> edges;

i64 kv_sum[mxn]; int col[mxn];
i64 sum_kv[mxn]; int chi[mxn];
int n, m;

int colour(int u) {
	if(col[u] < 0) return u;
	return col[u] = colour(col[u]);
}

bool unite(int u, int v) {
	u = colour(u);
	v = colour(v);
	if(u == v) return 0;

	if(col[u] > col[v]) swap(u, v);
	col[u] += col[v];
	col[v] = u;
	return 1;
}

bool vis[mxn];
i64 ans = 0;
void dfs(int u, int par) {
	vis[u] = 1;
	for(int v : adj[u]) {
		if(v == par) continue;
		if(vis[v]) continue;
		dfs(v, u);
		chi[u] += chi[v];
		kv_sum[u] += chi[v] * chi[v];
		sum_kv[u] += chi[v];
	}

	sum_kv[u] *= sum_kv[u];
	chi[u]++;

	i64 t = sum_kv[u] - kv_sum[u];
	ans += t / 2;

	i64 total = -col[colour(u)];
	i64 s = total - chi[u];
	i64 f = chi[u] - 1;
	ans += s * f;

	// cout << "node: " << u << endl;
	// cout << sum_kv[u] * sum_kv
}

int32_t main() {
	cin >> n >> m;
	memset(col, -1, sizeof col);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		unite(u, v);
	}

	for(int u = 1; u <= n; u++)
		if(!vis[u])
			dfs(u, u);
	cout << 2 * ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 22352 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 11356 KB Output is correct
2 Correct 3 ms 11412 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 3 ms 11416 KB Output is correct
5 Correct 4 ms 11356 KB Output is correct
6 Correct 3 ms 11356 KB Output is correct
7 Correct 4 ms 11356 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 3 ms 11356 KB Output is correct
10 Correct 4 ms 11416 KB Output is correct
11 Correct 3 ms 11356 KB Output is correct
12 Correct 3 ms 11416 KB Output is correct
13 Correct 3 ms 11356 KB Output is correct
14 Correct 3 ms 11356 KB Output is correct
15 Correct 3 ms 11356 KB Output is correct
16 Correct 3 ms 11436 KB Output is correct
17 Correct 3 ms 11412 KB Output is correct
18 Correct 3 ms 11356 KB Output is correct
19 Correct 3 ms 11356 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15196 KB Output is correct
2 Correct 88 ms 16464 KB Output is correct
3 Correct 60 ms 16480 KB Output is correct
4 Correct 94 ms 16384 KB Output is correct
5 Correct 95 ms 16720 KB Output is correct
6 Correct 67 ms 20088 KB Output is correct
7 Correct 79 ms 19008 KB Output is correct
8 Correct 69 ms 18260 KB Output is correct
9 Correct 61 ms 17748 KB Output is correct
10 Correct 73 ms 16744 KB Output is correct
11 Correct 59 ms 16468 KB Output is correct
12 Correct 60 ms 16464 KB Output is correct
13 Correct 65 ms 16468 KB Output is correct
14 Correct 62 ms 16060 KB Output is correct
15 Correct 50 ms 15700 KB Output is correct
16 Correct 42 ms 14420 KB Output is correct
17 Correct 54 ms 16816 KB Output is correct
18 Correct 73 ms 16604 KB Output is correct
19 Correct 53 ms 16536 KB Output is correct
20 Correct 59 ms 16744 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15184 KB Output is correct
2 Correct 62 ms 16360 KB Output is correct
3 Incorrect 86 ms 17012 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 11356 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 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -