Submission #502962

# Submission time Handle Problem Language Result Execution time Memory
502962 2022-01-06T20:34:53 Z sliviu Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
1 ms 332 KB
#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int construct(vector<vector<int>> p) {
	int n = p.size(), cur = 0;
	vector<vector<int>> ans(n, vector<int>(n));
	vector<int> seen(n), solved(n), cycle;
	function<void(int)> dfs = [&](int node) {
		seen[node] = cur;
		int c1 = 0, c2 = 0;
		for (int i = 0; i < n; ++i)
			if (i != node) {
				if (p[node][i] == 1)
					++c1;
				else if (p[node][i] == 2)
					++c2;
				else if (p[node][i] == 3)
					return 0;
				if (!seen[i] && p[node][i])
					dfs(i);
				if (!p[node][i] && seen[i])
					return 0;
			}
		if (!c1 && c2)
			cycle.emplace_back(node);
		if (!solved[cur] && c1) {
			solved[cur] = 1;
			int cur = node;
			for (int i = 0; i < n; ++i)
				if (i != node && p[node][i] == 1)
					ans[cur][i] = ans[i][cur] = 1, cur = i;
		}
	};
	for (int i = 0; i < n; ++i)
		if (!seen[i]) {
			cycle.clear();
			++cur;
			dfs(i);
			if (!cycle.empty()) {
				int cur = i;
				for (auto x : cycle)
					if (x != i) {
						ans[cur][x] = ans[x][cur] = 1;
						cur = x;
					}
				ans[cur][i] = ans[i][cur] = 1;
			}
		}
	build(ans);
	return 1;
}

Compilation message

supertrees.cpp: In lambda function:
supertrees.cpp:35:2: warning: control reaches end of non-void function [-Wreturn-type]
   35 |  };
      |  ^
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -