| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317726 | amunduzbaev | Connecting Supertrees (IOI20_supertrees) | C++14 | 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 "grader.cpp"
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
const int N=1005;
int used[N];
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int> > b(n), ones(n), twos(n);
for(int i=0;i<n;i++){
b[i].resize(n);
for(int j=0;j<n;j++){
b[i][j] = 0;
if(i!=j && p[i][j] == 1)
ones[i].pb(j);
if(i!=j && p[i][j] == 2)
twos[i].pb(j);
if(p[i][j] == 3) return 0;
}
for(int j=0;j<ones[i].size(); j++){
for(int l=j+1;l<ones[i].size();l++)
if(p[ones[i][j]][ones[i][l]] != 1) return 0;
for(int l=0;l<twos[i].size();l++)
if(p[ones[i][j]][twos[i][l]] != 2) return 0;
}
if(twos[i].size() == 1) return 0;
for(int j=0;j<twos[i].size(); j++){
for(int l=0;l<ones[i].size();l++)
if(p[twos[i][j]][ones[i][l]] != 2) return 0;
for(int l=j+1;l<twos[i].size();l++)
if(p[twos[i][j]][twos[i][l]] != 2) return 0;
}
}
for(int i=0;i<n;i++){
if(used[i]) continue;
for(int j=0;j<ones[i].size();j++){
used[ones[i][j]] = 1;
b[i][ones[i][j]] = 1;
b[ones[i][j]][i] = 1;
}
if(twos[i].size() == 0) continue;
int j = 0, sz = twos[i].size();
b[i][twos[i][j]] = 1;
b[twos[i][j]][i] = 1;
for(;j<sz-1; j++){
used[twos[i][j]] = 1;
b[twos[i][j]][twos[i][j+1]] = 1;
b[twos[i][j+1]][twos[i][j]] = 1;
}
used[twos[i][j]] = 1;
b[i][twos[i][j]] = 1;
b[twos[i][j]][i] = 1;
}
build(b);
return 1;
return 0;
}
/*
5
0 2 2 2 2
2 0 2 2 2
2 2 0 2 2
2 2 2 0 2
2 2 2 2 0
3
1 2 2
2 1 2
2 2 1
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
5
1 2 2 2 0
2 1 2 2 0
2 2 1 2 0
2 2 2 1 0
0 0 0 0 1
*/