| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 313559 | mohamedsobhi777 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 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 <bits/stdc++.h>
#include <vector>
using namespace std;
std::vector<std::vector<int>> answer;
int vis[100000];
bool bad;
int nn;
vector<int> vecs(int x)
{
vector<int> ret;
queue<int> qu;
qu.push(x);
while (qu.size())
{
int x = qu.front();
qu.pop();
if (vis[x]++)
continue;
ret.push_back(x);
for (int i = 0; i < n; ++i)
{
if (i == x || vis[i] || !p[x][i])
continue;
qu.push(i);
}
}
return ret;
}
void solve(vector<int> vecs)
{
if (!vecs.size())
return;
int sz = (int)vecs.size();
vector<int> cycle, line;
for (int i = 0; i < sz; ++i)
{
for (int j = 0; j < sz; ++j)
{
if (i == j)
continue;
if (p[vecs[i]][vecs[j]] != 2)
{
line.push_back(i);
break;
}
}
if (line.empty() || line.back() != i)
cycle.push_back(i);
}
if (cycle.size() == 1)
bad = 1;
if (line.size() && cycle.size())
cycle.push_back(line[0]);
for (int i = 0; i < (int)cycle.size(); ++i)
{
}
for (int i = 1; i < (int)line.size(); ++i)
{
int x = vecs[line[i]], y = vecs[line[i - 1]];
answer[x][y] = answer[y][x] = 1;
}
for (int i = 0; i < line.size(); ++i)
{
for (int j = 0; j < line.size(); ++j)
{
if (i == j)
continue;
if (p[vecs[i]][vecs[j]] != 1)
bad = 1;
}
}
}
int construct(std::vector<std::vector<int>> p)
{
nn = p.size();
for (int i = 0; i < nn; i++)
{
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i = 0; i < nn; ++i)
{
vector<int> g = vecs(i);
solve(g);
}
if (bad)
return 0;
build(answer);
return 1;
}