| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 927618 | MrDeboo | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
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;
}
vector<int>vct[1000][2];
vector<vector<int>>ans;
vector<vector<int>>P;
int slv(vector<int>v){
cerr<<'f';
for(auto &i:v){
for(auto &w:v){
if(!p[i][w])return 0;
}
}
vector<int>V;
vector<bool>vis(p.size());
for(int i=0;i<v.size();i++){
if(vis[i])continue;
int I=i;
for(int w=0;w<v.size();w++){
if(P[v[i]][v[w]]==1&&!vis[w]&&i!=w){
bool bl=1;
for(int j=0;j<v.size();j++){
if(j==i||j==w)continue;
if(P[v[j]][v[i]]!=P[v[j]][v[w]])bl=0;
}
if(bl){
vis[w]=1;
ans[v[I]][v[w]]=1;
ans[v[w]][v[I]]=1;
I=w;
}
}
}
V.push_back(v[i]);
vis[i]=1;
}
v=V;
for(int i=0;i<v.size();i++){
for(int w=i+1;w<v.size();w++){
if(P[v[i]][v[w]]!=2)return 0;
}
}
if(v.size()>1){
if(v.size()==2)return 0;
for(int i=0;i<v.size();i++){
ans[v[i]][v[(i+1)%v.size()]]=1;
ans[v[(i+1)%v.size()]][v[i]]=1;
}
}
return 1;
}
int construct(std::vector<std::vector<int>> p){
for(auto &i:p){
for(auto &w:i){
if(w>2)return 0;
}
}
for(auto &i:p)P.push_back(i);
int n=p.size();
for(int i=0;i<n;i++){
for(int w=0;w<n;w++){
if(i==w)continue;
vct[i][p[i][w]-1].push_back(w);
}
}
for(int i=0;i<n;i++){
vector<int>v(n);
ans.push_back(v);
}
vector<bool>vis(n);
for(int i=0;i<n;i++){
for(int w=0;w<n;w++){
if(vis[i]||vis[w]||i==w)continue;
if(p[i][w]){
deque<int>dq={i};
vis[i]=1;
vector<int>vc;
while(dq.size()){
int a=dq.front();
vc.push_back(a);
dq.pop_front();
for(auto &j:vct[a][1]){
if(!vis[j]){
vis[j]=1;
dq.push_back(j);
}
}
for(auto &j:vct[a][0]){
if(!vis[j]){
vis[j]=1;
dq.push_back(j);
}
}
}
if(!slv(vc))return 0;
}
}
}
build(ans);
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);
}