| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 329504 | blue | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
using namespace std;
int construct(vector< vector<int> > p)
{
int n = p.size();
vector<int> chain(n, -1), ring(n, -1);
for(int i = 0; i < n; i++) chain[i] = ring[i] = i;
for(int j = 0; j < n; j++)
{
for(int i = 0; i < j; i++)
{
if(p[i][j] >= 1)
{
ring[j] = ring[i];
break;
}
}
for(int i = 0; i < j; i++)
{
if(p[i][j] == 1)
{
chain[j] = chain[i];
break;
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++)
{
if(chain)
if(p[i][j] == 0)
{
if(chain[i] == chain[j]) return 0;
if(ring[i] == ring[j]) return 0;
}
else if(p[i][j] == 1)
{
if(chain[i] != chain[j]) return 0;
if(ring[i] != ring[j]) return 0;
}
else if(p[i][j] == 2)
{
if(chain[i] == chain[j]) return 0;
if(ring[i] != ring[j]) return 0;
}
else if(p[i][j] == 3)
{
return 0;
}
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
{
if(p[i][j] == 0 && p[j][k] > 0 && p[k][i] > 0) return 0;
if(p[i][j] == 1 && p[j][k] == 1 && p[k][i] != 1) return 0;
if(p[i][j] >= 1 && p[j][k] >= 1 && p[k][i] == 0) return 0;
}
vector< vector<int> > b (n, vector<int>(n, 0));
vector<int> oncycle(n, 1);
for(int i = 0; i < n; i++)
{
for(int j = i-1; j >= 0; j--)
if(p[i][j] == 1)
{
oncycle[i] = 0;
b[i][j] = b[j][i] = 1;
break;
}
}
int pre;
for(int i = 0; i < n; i++)
{
if(!oncycle[i]) continue;
pre = i;
oncycle[i] = 0;
for(int j = i+1; j < n; j++)
{
if(!oncycle[j]) continue;
if(p[pre][j] == 2)
{
b[pre][j] = b[j][pre] = 1;
pre = j;
oncycle[j] = 0;
}
}
if(pre != i) b[pre][i] = b[i][pre] = 1;
}
build(b);
return 1;
}