oj.uz

답안 #727695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727695 2023-04-21T06:22:51 Z SanguineChameleon 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 129 ms 27360 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;
vector<int> comp_color[maxn];
int color[maxn];
int sz_color[maxn];
int sz_color_sub[maxn];
int sz_color_root[maxn];
long long sz_color_sum[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[u].push_back(v);
			}
		}
		comp_color[color[u]].push_back(u);
	}
}

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) {
	comp.push_back(color[u]);
	sz_color_sub[color[u]] = sz_color[color[u]];
	int rem = node_cnt - sz_color[color[u]];
	for (auto v: comp_color[color[u]]) {
		for (auto x: ch_color[v]) {
			dfs4(x);
			sz_color_sub[color[u]] += sz_color_sub[color[x]];
			sz_color_root[v] += sz_color_sub[color[x]];
			sz_color_sum[v] -= 1LL * sz_color_sub[color[x]] * sz_color_sub[color[x]];
			rem -= sz_color_sub[color[x]];
		}
	}
	sz_color_root[u] += rem;
	sz_color_sum[u] -= 1LL * rem * rem;
	for (auto v: comp_color[color[u]]) {
		sz_color_sum[v] += 1LL * sz_color_root[v] * sz_color_root[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);
	}
	dfs4(root);
	long long res = 0;
	for (auto u: comp) {
		res += 1LL * sz_color[u] * (sz_color[u] - 1) * (sz_color[u] - 2);
		res += 1LL * (sz_color[u] - 1) * (sz_color[u] - 1) * (node_cnt - sz_color[u]) * 2;
		res += 1LL * sz_color[u] * (node_cnt - sz_color[u]) * (node_cnt - sz_color[u]);
		for (auto v: comp_color[u]) {
			res -= 1LL * sz_color[u] * sz_color_root[v] * sz_color_root[v];
			res += sz_color_sum[v];
		}
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 24488 KB Output is correct
2 Correct 65 ms 24532 KB Output is correct
3 Correct 129 ms 23644 KB Output is correct
4 Correct 83 ms 25032 KB Output is correct
5 Correct 79 ms 20872 KB Output is correct
6 Correct 92 ms 22192 KB Output is correct
7 Correct 108 ms 20800 KB Output is correct
8 Correct 99 ms 21720 KB Output is correct
9 Correct 99 ms 19532 KB Output is correct
10 Correct 99 ms 19932 KB Output is correct
11 Correct 69 ms 17584 KB Output is correct
12 Correct 75 ms 17580 KB Output is correct
13 Correct 83 ms 17560 KB Output is correct
14 Correct 84 ms 17440 KB Output is correct
15 Correct 55 ms 17532 KB Output is correct
16 Correct 49 ms 17228 KB Output is correct
17 Correct 15 ms 14420 KB Output is correct
18 Correct 14 ms 14420 KB Output is correct
19 Correct 15 ms 14404 KB Output is correct
20 Correct 14 ms 14356 KB Output is correct
21 Correct 14 ms 14292 KB Output is correct
22 Correct 13 ms 14292 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7536 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7636 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7540 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 4 ms 7508 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 4 ms 7508 KB Output is correct
17 Correct 4 ms 7508 KB Output is correct
18 Correct 4 ms 7508 KB Output is correct
19 Correct 4 ms 7508 KB Output is correct
20 Correct 4 ms 7508 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 20044 KB Output is correct
2 Correct 91 ms 19912 KB Output is correct
3 Correct 91 ms 19912 KB Output is correct
4 Correct 98 ms 20000 KB Output is correct
5 Correct 100 ms 19916 KB Output is correct
6 Correct 112 ms 27360 KB Output is correct
7 Correct 106 ms 24568 KB Output is correct
8 Correct 114 ms 23372 KB Output is correct
9 Correct 112 ms 22352 KB Output is correct
10 Correct 110 ms 19580 KB Output is correct
11 Correct 113 ms 19684 KB Output is correct
12 Correct 94 ms 19432 KB Output is correct
13 Correct 114 ms 19440 KB Output is correct
14 Correct 79 ms 19204 KB Output is correct
15 Correct 76 ms 19244 KB Output is correct
16 Correct 49 ms 18080 KB Output is correct
17 Correct 56 ms 19140 KB Output is correct
18 Correct 56 ms 19188 KB Output is correct
19 Correct 60 ms 19016 KB Output is correct
20 Correct 63 ms 19108 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 6 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7472 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Correct 4 ms 7400 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 4 ms 7504 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 4 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 4 ms 7508 KB Output is correct
19 Incorrect 4 ms 7508 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 19908 KB Output is correct
2 Correct 109 ms 20268 KB Output is correct
3 Correct 93 ms 18552 KB Output is correct
4 Correct 86 ms 18660 KB Output is correct
5 Correct 79 ms 17484 KB Output is correct
6 Correct 69 ms 17096 KB Output is correct
7 Correct 63 ms 16940 KB Output is correct
8 Correct 59 ms 16608 KB Output is correct
9 Correct 67 ms 16644 KB Output is correct
10 Correct 63 ms 16596 KB Output is correct
11 Correct 57 ms 16500 KB Output is correct
12 Correct 51 ms 16580 KB Output is correct
13 Correct 64 ms 16660 KB Output is correct
14 Correct 64 ms 18584 KB Output is correct
15 Correct 107 ms 25004 KB Output is correct
16 Correct 109 ms 23196 KB Output is correct
17 Correct 104 ms 23616 KB Output is correct
18 Correct 102 ms 21944 KB Output is correct
19 Correct 89 ms 18516 KB Output is correct
20 Correct 93 ms 18272 KB Output is correct
21 Correct 87 ms 18228 KB Output is correct
22 Incorrect 102 ms 17880 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -