oj.uz

Submission #727606

# Submission time Handle Problem Language Result Execution time Memory
727606 2023-04-21T02:50:17 Z SanguineChameleon Duathlon (APIO18_duathlon) C++17
0 / 100
 47 ms 7104 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];
bool can[55][55][55];
bool bad[maxn];
bool flag[maxn];
int n, m;

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

void sub1() {
	for (int x = 1; x <= n; x++) {
		for (int a = 1; a <= n; a++) {
			if (a != x) {
				dfs(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 just_do_it() {
	cin >> n >> m;
	assert(m >= n - 1);
	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) {
		sub1();
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Runtime error 4 ms 5204 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Runtime error 4 ms 5204 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 6908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 7052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 7104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Runtime error 4 ms 5204 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Runtime error 4 ms 5204 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -