#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define ROF(i,a,b) for (int i=(a); i>=(b); i--)
#define gay cout << "gay";
bool visited[1005];
int parent[1005], n;
vector<vector<int> > answer, pp;
int fp(int a){
if (a == parent[a]) return a;
else return parent[a] = fp(parent[a]);
}
bool join(int a, int b){
int pa = fp(a);
int pb = fp(b);
if (pa!=pb) {
parent[b] = a;
return 1;
} else return 0;
}
void dfs(int u, int start){
visited[fp(u)] = 1;
bool check=0;
FOR(i,0,n-1){
if (pp[u][i] != 2) continue;
else if (!visited[fp(i)]) {
answer[u][i] = answer[i][u] = 1;
dfs(i, start);
check = 1;
}
}
if (!check) answer[u][start] = answer[start][u] = 1;
return;
}
vector<vector<int> > chk;
bool visiting[1005];
void dfscheck(int u, int start){
//cout << u << '\n';
visiting[u] = 1;
chk[start][u]++;
FOR(i,0,n-1){
if (!answer[u][i]) continue;
if (!visiting[i]) dfscheck(i, start);
}
visiting[u] = 0;
return;
}
bool test(){
FOR(i,0,n-1){
visiting[i] = 0;
vector<int> row;
row.resize(n);
chk.push_back(row);
FOR(j,0,n-1) chk[i][j] = 0;
}
FOR(i,0,n-1){
dfscheck(i,i);
}
/*
FOR(i,0,n-1){
FOR(j,0,n-1){
cout << chk[i][j] << " ";
}
cout << '\n';
}
*/
if (chk == pp) return 1;
else return 0;
}
int construct(vector<vector<int> > p){
pp = p;
n = p.size();
FOR(i,0,n-1){
parent[i] = i;
visited[i] = 0;
}
answer.clear();
FOR(i,0,n-1){
vector<int> row;
row.resize(n);
answer.push_back(row);
}
bool imposs=0;
FOR(i,0,n-1) {
FOR(j,0,n-1){
if (i==j && p[i][j] != 1) imposs=1;
if (p[i][j] != p[j][i]) imposs=1;
if (p[i][j] == 3) imposs=1;
if (imposs) break;
if (p[i][j] == 1 && join(i,j)) answer[i][j] = answer[j][i] = 1;
}
if (imposs) break;
}
if (imposs) return 0;
FOR(i,0,n-1){
if (!visited[fp(i)]) dfs(i,i);
}
if (test()) {
build(answer);
return 1;
} else return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
