이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e3 + 1;
int N;
int P[NMAX][NMAX];
int head[NMAX];
bool Edge[NMAX][NMAX];
vector < int > roots;
vector < int > List[NMAX];
bool OK = 1;
class DisjointSets
{
int T[NMAX], Size[NMAX];
private:
inline int Find (int X)
{
if(X == T[X])
return X;
return (T[X] = Find(T[X]));
}
inline void my_swap (int &x, int &y)
{
x = (x ^ y), y = (x ^ y), x = (x ^ y);
return;
}
public:
inline void Initialize (int N)
{
for(int i = 1; i <= N; ++i)
T[i] = i, Size[i] = 1;
return;
}
inline bool Unify (int X, int Y)
{
X = Find(X), Y = Find(Y);
if(X == Y)
return 0;
if(Size[X] < Size[Y])
my_swap(X, Y);
Size[X] += Size[Y], Size[Y] = 0;
T[Y] = X;
return 1;
}
inline int Who_is_the_boss (int Node)
{
return Find(Node);
}
} DSU, cycles;
void Build_type_1 ()
{
DSU.Initialize(N);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(P[i][j] == 1)
DSU.Unify(i, j);
for(int i = 1; i <= N; ++i)
{
head[i] = DSU.Who_is_the_boss(i);
if(i == head[i])
roots.push_back(i);
else
Edge[i][head[i]] = Edge[head[i]][i] = 1;
}
return;
}
void Build_type_2 ()
{
cycles.Initialize(N);
for(int i = 0; i < (int)roots.size() - 1; ++i)
for(int j = i + 1; j < (int)roots.size(); ++j)
if(P[roots[i]][roots[j]] == 2)
cycles.Unify(roots[i], roots[j]);
for(auto it : roots)
{
int rep = cycles.Who_is_the_boss(it);
List[rep].push_back(it);
}
for(int i = 1; i <= N; ++i)
if((int)List[i].size() > 2)
{
for(int j = 0; j < (int)List[i].size() - 1; ++j)
Edge[List[i][j]][List[i][j + 1]] = Edge[List[i][j + 1]][List[i][j]] = 1;
/*
for(int j = 0; j < (int)List[i].size() - 1; ++j)
for(int k = j + 1; k < (int)List[i].size(); ++k)
if(P[List[i][j]][List[i][k]] != 2)
OK = 0;
*/
int First = List[i][0];
int Last = List[i][(int)List[i].size() - 1];
Edge[First][Last] = Edge[Last][First] = 1;
}
else if((int)List[i].size() == 1 || (int)List[i].size() == 2)
OK = 0;
return;
}
int construct (vector < vector < int > > p)
{
N = (int)p.size();
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
{
P[i + 1][j + 1] = p[i][j];
if(p[i][j] == 3)
return 0;
}
Build_type_1();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(P[i][j] == 0)
if(head[i] == head[j])
return 0;
Build_type_2();
if(!OK)
return 0;
///
vector < vector < int > > ans;
for(int i = 0; i < N; ++i)
{
vector < int > _temp;
for(int j = 0; j < N; ++j)
if(Edge[i + 1][j + 1])
_temp.push_back(1);
else
_temp.push_back(0);
ans.push_back(_temp);
}
build(ans);
///
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |