| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 952780 | emad234 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
int dsu[mxN];
int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
void merge(int a, int b) { dsu[find(b)] = find(a); }
int construct(std::vector<std::vector<int>> p)
{
vector<vector<int>> b;
int n = p.size(), m = p.size();
b.resize(n);
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < n; i++)
b[i].resize(m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (p[i][j] == 1)
{
if (find(i) != find(j))
{
merge(i, j);
b[i][j] = 1;
b[j][i] = 1;
}
}
}
}
vector<vector<int>> ty;
vector<set<int>> v;
v.resize(n);
ty.resize(n);
for (int i = 0; i < n; i++)
{
ty[i].resize(n);
for (int j = 0; j < m; j++)
{
ty[i][j] = -1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (find(i) == find(j))
{
if (p[i][j] != 1)
return 0;
}
else
{
if (ty[find(i)][find(j)] != -1 && p[i][j] != ty[find(i)][find(j)])
return 0;
if (p[i][j] == 2)
{
v[find(i)].insert(find(j));
v[find(j)].insert(find(i));
}
ty[find(i)][find(j)] = p[i][j];
}
}
}
vector<bool> vis(n);
for (int i = 0; i < n; i++)
{
int prv = -1;
if (vis[i])
continue;
if (v[i].size() == 1)
return 0;
v[i].insert(i);
for (auto x : v[i])
{
for (int j = 0; j < n; j++)
{
if (x == j)
continue;
if (v[i].find(j) != v[i].end() && p[x][j] != 2)
return 0;
}
}
for (auto x : v[i])
{
vis[x] = 1;
if (prv != -1)
{
b[x][prv] = 1;
b[prv][x] = 1;
}
prv = x;
}
if (v[i].size() >= 2)
{
b[*v[i].begin()][*v[i].rbegin()] = 1;
b[*v[i].rbegin()][*v[i].begin()] = 1;
}
}
build(b);
return 1;
}