oj.uz

Submission #727666

# Submission time Handle Problem Language Result Execution time Memory
727666 2023-04-21T05:33:38 Z SanguineChameleon Duathlon (APIO18_duathlon) C++17
31 / 100
 88 ms 21176 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 1e5 + 20;
vector<int> adj[maxn];
vector<int> ch_color[maxn];
vector<int> comp;
int color[maxn];
int sz_color[maxn];
int sz_color_sub[maxn];
bool can[55][55][55];
bool bad[maxn];
bool flag[maxn];
int par[maxn];
int depth[maxn];
int high[maxn];
int sz[maxn];
int node_cnt = 0;
int edge_cnt = 0;
int n, m;

void dfs1(int x, int a, int b) {
	can[x][a][b] = true;
	for (auto c: adj[b]) {
		if (c != x && !can[x][a][c]) {
			dfs1(x, a, c);
		}
	}
}

void dfs2(int u, int p, bool sub7 = false) {
	color[u] = u;
	sz_color[u] = 1;
	par[u] = p;
	high[u] = depth[u];
	flag[u] = true;
	node_cnt++;
	edge_cnt += adj[u].size();
	sz[u] = 1;
	for (auto v: adj[u]) {
		if (v == p) {
			continue;
		}
		if (!flag[v]) {
			depth[v] = depth[u] + 1;
			dfs2(v, u, sub7);
			sz[u] += sz[v];
			high[u] = min(high[u], high[v]);
		}
		else {
			high[u] = min(high[u], depth[v]);
			if (depth[u] > depth[v] && sub7) {
				int cur = u;
				while (true) {
					sz_color[color[cur]]--;
					color[cur] = u;
					sz_color[color[cur]]++;
					if (cur == v) {
						break;
					}
					cur = par[cur];
				}
			}
		}
	}
	if (sub7) {
		for (auto v: adj[u]) {
			if (par[v] == u && color[v] != color[u]) {
				ch_color[color[u]].push_back(color[v]);
			}
		}
	}
}

void sub1() {
	for (int x = 1; x <= n; x++) {
		for (int a = 1; a <= n; a++) {
			if (a != x) {
				dfs1(x, a, a);
			}
		}
		bad[x] = false;
	}
	int res = 0;
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= n; b++) {
			if (b == a) {
				continue;
			}
			for (int c = 1; c <= n; c++) {
				if (c == a || c == b) {
					continue;
				}
				bool ok = true;
				for (int x = 1; x <= n; x++) {
					if (x == b) {
						continue;
					}
					if (!can[x][a][b] && !can[x][b][c]) {
						ok = false;
						break;
					}
				}
				if (ok) {
					res++;
				}
			}
		}
	}
	cout << res;
}

void dfs4(int u) {
	node_cnt++;
	comp.push_back(u);
	sz_color_sub[u] = sz_color[u];
	for (auto v: ch_color[u]) {
		dfs4(v);
		sz_color_sub[u] += sz_color_sub[v];
	}
}

long long solve(int root) {
	comp.clear();
	node_cnt = 0;
	edge_cnt = 0;
	dfs2(root, -1, true);
	edge_cnt /= 2;
	if (node_cnt == edge_cnt) {
		return 1LL * node_cnt * (node_cnt - 1) * (node_cnt - 2);
	}
	node_cnt = 0;
	edge_cnt = 0;
	dfs4(color[root]);
	long long res = 0;
	for (auto u: comp) {
		res += 1LL * sz_color_sub[u] * (node_cnt - sz_color_sub[u]) * 2;
	}
	res -= 1LL * node_cnt * (node_cnt - 1);
	return res;
}

long long dfs3(int u) {
	int cnt = 1;
	for (auto v: adj[u]) {
		if (par[v] == u && high[v] >= depth[u]) {
			cnt += sz[v];
		}
	}
	long long res = 1LL * cnt * (cnt - 1);
	for (auto v: adj[u]) {
		if (par[v] == u && high[v] < depth[u]) {
			res += dfs3(v);
		}
	}
	return res;
}

void sub8() {
	long long res = 0;
	for (int u = 1; u <= n; u++) {
		node_cnt = 0;
		for (int i = 1; i <= n; i++) {
			flag[i] = false;
		}
		depth[u] = 0;
		dfs2(u, -1);
		res += 1LL * (node_cnt - 1) * (node_cnt - 2);
		for (auto v: adj[u]) {
			if (par[v] == u) {
				res -= dfs3(v);
			}
		}
	}
	cout << res;
}

void just_do_it() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	if (n <= 50 && false) {
		sub1();
		return;
	}
	if (n <= 1000 && false) {
		sub8();
		return;
	}
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		if (!flag[i]) {
			res += solve(i);
		}
	}
	cout << res;
	return;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 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 4948 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 61 ms 21100 KB Output is correct
2 Correct 72 ms 21176 KB Output is correct
3 Correct 72 ms 18824 KB Output is correct
4 Correct 66 ms 20280 KB Output is correct
5 Correct 69 ms 16756 KB Output is correct
6 Correct 70 ms 17424 KB Output is correct
7 Correct 78 ms 16000 KB Output is correct
8 Correct 77 ms 16772 KB Output is correct
9 Correct 77 ms 15096 KB Output is correct
10 Correct 73 ms 15656 KB Output is correct
11 Correct 52 ms 13060 KB Output is correct
12 Correct 48 ms 12980 KB Output is correct
13 Correct 45 ms 12748 KB Output is correct
14 Correct 47 ms 12660 KB Output is correct
15 Correct 34 ms 11992 KB Output is correct
16 Correct 32 ms 11872 KB Output is correct
17 Correct 7 ms 7764 KB Output is correct
18 Correct 5 ms 7764 KB Output is correct
19 Correct 5 ms 7636 KB Output is correct
20 Correct 5 ms 7764 KB Output is correct
21 Correct 5 ms 7636 KB Output is correct
22 Correct 6 ms 7700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5032 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5172 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5060 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5036 KB Output is correct
15 Correct 3 ms 5028 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5036 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14508 KB Output is correct
2 Correct 68 ms 14572 KB Output is correct
3 Correct 67 ms 14500 KB Output is correct
4 Correct 59 ms 14584 KB Output is correct
5 Correct 63 ms 14496 KB Output is correct
6 Correct 81 ms 21120 KB Output is correct
7 Correct 88 ms 18576 KB Output is correct
8 Correct 72 ms 17584 KB Output is correct
9 Correct 72 ms 16584 KB Output is correct
10 Correct 70 ms 14084 KB Output is correct
11 Correct 72 ms 14396 KB Output is correct
12 Correct 71 ms 14016 KB Output is correct
13 Correct 68 ms 13956 KB Output is correct
14 Correct 59 ms 13736 KB Output is correct
15 Correct 51 ms 13480 KB Output is correct
16 Correct 36 ms 12080 KB Output is correct
17 Correct 38 ms 13700 KB Output is correct
18 Correct 35 ms 13608 KB Output is correct
19 Correct 35 ms 13580 KB Output is correct
20 Correct 37 ms 13632 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13736 KB Output is correct
2 Correct 65 ms 13844 KB Output is correct
3 Incorrect 86 ms 13268 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 4948 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 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -