| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 432346 | arayi | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
#define ad push_back
using namespace std;
const int N = 1111;
int col[N], sm[N], i1 = 1;
vector <vector <int> > b;
vector<int> g[N];
int n;
void dfs(int v)
{
col[v] = 2;
sm[v]++;
for(auto p : g[v])
if(col[i] != 2 && b[v][i]) dfs(i);
col[v] = 1;
}
int construct(std::vector<std::vector<int>> p) {
n = p.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if(p[i][j] > 3) return 0;
for (int i = 0; i < n; i++)
{
if(sm[i])
{
for (int j = 0; j < n; j++)
{
if(p[i][j] && sm[i] != sm[j]) return 0;
if(p[i][j] == 0 && sm[i] == sm[j]) return 0;
}
}
else
{
for (int j = 0; j < n; j++)
{
if(p[i][j] && sm[j]) return 0;
if(p[i][j]) sm[j] = i1;
}
}
i1++;
}
b.resize(n);
for (int i = 0; i < n; i++) b[i].resize(n);
for (int i = 1; i < i1; i++)
{
vector<int> fp;
for (int j = 0; j < n; j++)
if(sm[j] == i) fp.ad(j);
int nx = -1;
for (int j = 0; j < fp.size(); j++)
{
if(col[fp[j]]) continue;
if(nx != -1) b[nx][fp[j]] = b[fp[j]][nx] = 1;
nx = fp[j];
col[fp[j]] = 1;
for (int k = j + 1; k < fp.size(); k++)
if(p[fp[j]][fp[k]] == 1) b[fp[j]][fp[k]] = b[fp[k]][fp[j]] = 1, col[fp[k]] = 1;
}
if(nx != -1 && nx != fp[0]) b[nx][fp[0]] = b[fp[0]][nx] = 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if(b[i][j]) g[i].ad(j);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) sm[j] = col[j] = 0;
dfs(i);
for (int j = 0; j < n; j++) if(sm[j] != p[i][j]) return 0;
}
build(b);
return 1;
}