# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
313161 | wasyl | Connecting Supertrees (IOI20_supertrees) | C++17 | 256 ms | 22200 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "supertrees.h"
#include <vector>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
//int n = p.size();
//std::vector<std::vector<int>> answer;
//for (int i = 0; i < n; i++) {
// std::vector<int> row;
// row.resize(n);
// answer.push_back(row);
//}
//build(answer);
//return 1;
int n = p.size();
vector< vector< int > > ans(n, vector< int >(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (p[i][j] == 3)
return 0;
vector< int > siv(n, false);
vector< int > vis(n, false);
for (int i = 0; i < n; ++i)
if (not vis[i])
{
vector< int > sub;
for (int j = 0; j < n; ++j)
if (p[i][j] and not vis[j])
sub.push_back(j);
else if (p[i][j] and vis[j]) return 0;
for (int a : sub)
for (int b : sub)
if (not p[a][b])
return 0;
for (int a : sub)
vis[a] = true;
vector< vector< int > > div;
for (int a : sub)
if (not siv[a])
{
div.push_back(vector< int >());
for (int b : sub)
if (p[a][b] == 1 and not siv[b])
div.back().push_back(b);
else if (p[a][b] == 1 and siv[b]) return 0;
for (int a : div.back())
siv[a] = true;
for (int a : div.back())
for (int b : sub)
if (not siv[b] and p[a][b] == 1)
return 0;
for (int a : div.back())
for (int b : div.back())
if (p[a][b] != 1)
return 0;
}
for (int i = 1; i < div.size(); ++i)
ans[div[i - 1][0]][div[i][0]] = ans[div[i][0]][div[i - 1][0]] = 1;
if (div.size() > 1)
ans[div.back()[0]][div.front()[0]] = ans[div.front()[0]][div.back()[0]] = 1;
for (const auto& vv : div)
for (int i = 1; i < vv.size(); ++i)
ans[vv[i]][vv[i - 1]] = ans[vv[i - 1]][vv[i]] = 1;
}
build(ans);
return 1;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |