oj.uz

답안 #300672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300672 2020-09-17T11:35:16 Z Temmie 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
 1000 ms 26232 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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