Submission #300672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300672	2020-09-17T11:35:16 Z	Temmie	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1000 ms	26232 KB

supertrees

#include <bits/stdc++.h>

void build(std::vector <std::vector <int>> b);

void ff1(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
	if (vis[node]) return;
	vis[node] = true;
	col.back().push_back(node);
	for (int i = 0; i < n; i++) {
		if (p[node][i] == 1) {
			ff1(i, n, p, col, vis);
		}
	}
}

void ff2(int node, int n, std::vector <std::vector <int>>& p, std::vector <std::vector <int>>& col, std::vector <bool>& vis) {
	if (vis[node]) return;
	vis[node] = true;
	col.back().push_back(node);
	for (int i = 0; i < n; i++) {
		if (p[node][i] == 2) {
			ff2(i, n, p, col, vis);
		}
	}
}

void dfs(int node, int n, std::vector <bool>& vis, std::vector <int>& cnt, std::vector <std::vector <int>>& g) {
	if (vis[node]) return;
	vis[node] = true;
	cnt[node]++;
	for (int i = 0; i < n; i++) {
		if (g[node][i]) {
			dfs(i, n, vis, cnt, g);
		}
	}
	vis[node] = false;
}

int construct(std::vector <std::vector <int>> p) {
	
	std::vector <std::vector <int>> ep(p);
	int n = p.size();
	std::vector <std::vector <int>> ocol;
	for (int i = 0; i < n; i++) {
		static std::vector <bool> vis(n, false);
		if (vis[i]) continue;
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 1) {
				ocol.push_back({ });
				ff1(i, n, p, ocol, vis);
				break;
			}
		}
	}
	for (auto& v : ocol) {
		for (size_t i = 1; i < v.size(); i++) {
			for (int j = 0; j < n; j++) {
				p[v[i]][j] = p[j][v[i]] = 0;
			}
			p[v[i]][v[i]] = 1;
		}
	}
	std::vector <std::vector <int>> tcol;
	for (int i = 0; i < n; i++) {
		static std::vector <bool> vis(n, false);
		if (vis[i]) continue;
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 2) {
				tcol.push_back({ });
				ff2(i, n, p, tcol, vis);
				break;
			}
		}
	}
	std::vector <std::vector <int>> ans(n, std::vector <int> (n, 0));
	for (auto& v : ocol) {
		for (size_t i = 0; i < v.size() - 1; i++) {
			ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
		}
	}
	for (auto& v : tcol) {
		for (size_t i = 0; i < v.size() - 1; i++) {
			ans[v[i]][v[i + 1]] = ans[v[i + 1]][v[i]] = 1;
		}
		ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1;
	}
	for (int i = 0; i < n; i++) {
		std::vector <bool> vis(n, false);
		std::vector <int> cnt(n, 0);
		dfs(i, n, vis, cnt, ans);
		for (int j = 0; j < n; j++) {
			if (ep[i][j] != cnt[j]) return 0;
		}
	}
	build(ans);
	return 1;
	
}

Subtask #1

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	19 ms	1408 KB	Output is correct
7	Execution timed out	1057 ms	24460 KB	Time limit exceeded

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	19 ms	1408 KB	Output is correct
7	Execution timed out	1057 ms	24460 KB	Time limit exceeded

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	10 ms	1408 KB	Output is correct
9	Correct	244 ms	26108 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	27 ms	1408 KB	Output is correct
13	Execution timed out	1060 ms	16248 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	65 ms	6776 KB	Output is correct
5	Correct	340 ms	26104 KB	Output is correct
6	Correct	247 ms	26104 KB	Output is correct
7	Correct	736 ms	26232 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	70 ms	6904 KB	Output is correct
10	Correct	431 ms	26104 KB	Output is correct
11	Correct	250 ms	26104 KB	Output is correct
12	Execution timed out	1064 ms	24568 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	19 ms	1408 KB	Output is correct
7	Execution timed out	1057 ms	24460 KB	Time limit exceeded

Subtask #6

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	19 ms	1408 KB	Output is correct
7	Execution timed out	1057 ms	24460 KB	Time limit exceeded