| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 952779 | 2024-03-24T19:22:28 Z | emad234 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;
static void check(bool cond, std::string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
void build(std::vector<std::vector<int>> _b) {
check(!called, "build is called more than once");
called = true;
check((int)_b.size() == n, "Invalid number of rows in b");
for (int i = 0; i < n; i++) {
check((int)_b[i].size() == n, "Invalid number of columns in b");
}
b = _b;
}
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;
}
int main() {
assert(scanf("%d", &n) == 1);
p.resize(n);
for (int i = 0; i < n; i++) {
p[i].resize(n);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
assert(scanf("%d", &p[i][j]) == 1);
}
}
fclose(stdin);
int possible = construct(p);
check(possible == 0 || possible == 1, "Invalid return value of construct");
if (possible == 1) {
check(called, "construct returned 1 without calling build");
} else {
check(!called, "construct called build but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j) {
printf(" ");
}
printf("%d", b[i][j]);
}
printf("\n");
}
}
fclose(stdout);
}