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;
vector<int> v[1001];
vector<int> graph[1001], trees[1001];
int group[1001], pa[1001];
bool visited[1001];
int find(int x){
if(pa[x] == x) return x;
return pa[x] = find(pa[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
pa[x] = y;
}
void dfs(int x, int cnt){
if(visited[x]) return;
visited[x] = true;
group[x] = cnt;
graph[cnt].push_back(x);
for(int i = 0;i < v[x].size();i++){
dfs(v[x][i], cnt);
}
}
int construct(vector<vector<int> > p){
for(int i = 0;i < p.size();i++){
pa[i] = i;
for(int j = 0;j < p[i].size();j++){
if(p[i][j]) v[i].push_back(j);
}
}
int cnt = 0;
for(int i = 0;i < p.size();i++){
if(visited[i]) continue;
dfs(i, cnt); cnt++;
}
for(int i = 0;i < cnt;i++){
int maxchk = 0;
bool chk[4] = {0, 0, 0, 0};
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j], maxi = 0;
for(int k = 0;k < p.size();k++){
if(x == k) continue;
chk[p[x][k]] = true;
maxi = max(maxi, p[x][k]);
maxchk = max(maxchk, p[x][k]);
if(p[x][k] && group[k] != group[x]) return 0;
if(!p[x][k] && group[k] == group[x]) return 0;
}
if(maxi != maxchk) return 0;
}
if(chk[2] && chk[3]) return 0;
}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] == 1) merge(x, v[x][k]);
}
}
}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] != 1 && find(x) == find(v[x][k])) return 0;
}
}
}
for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
vector<vector<int> > b(p.size());
for(int i = 0;i < p.size();i++) b[i].resize(p.size(), 0);
for(int i = 0;i < p.size();i++){
if(trees[i].size() == 1) continue;
for(int j = 0;j < trees[i].size() - 1;j++){
b[trees[i][j]][trees[i][j+1]] = 1;
b[trees[i][j+1]][trees[i][j]] = 1;
}
b[trees[i].back()][trees[i][0]] = 1;
b[trees[i][0]][trees[i].back()] = 1;
}
for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] == 2) merge(x, v[x][k]);
}
}
}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] != 2 && find(x) == find(v[x][k])) return 0;
}
}
}
for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
for(int i = 0;i < p.size();i++){
if(trees[i].size() == 1) continue;
for(int j = 0;j < trees[i].size() - 1;j++){
b[trees[i][j]][trees[i][j+1]] = 1;
b[trees[i][j+1]][trees[i][j]] = 1;
}
b[trees[i].back()][trees[i][0]] = 1;
b[trees[i][0]][trees[i].back()] = 1;
}
for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] == 3) merge(x, v[x][k]);
}
}
}
for(int i = 0;i < cnt;i++){
for(int j = 0;j < graph[i].size();j++){
int x = graph[i][j];
for(int k = 0;k < v[x].size();k++){
if(x == v[x][k]) continue;
if(p[x][v[x][k]] != 3 && find(x) == find(v[x][k])) return 0;
}
}
}
for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
for(int i = 0;i < p.size();i++){
if(pa[i] != i) continue;
if(trees[i].size() == 1) continue;
if(trees[i].size() == 3) return 0;
for(int j = 0;j < trees[i].size() - 1;j++){
b[trees[i][j]][trees[i][j+1]] = 1;
b[trees[i][j+1]][trees[i][j]] = 1;
}
b[trees[i].back()][trees[i][0]] = 1;
b[trees[i][0]][trees[i].back()] = 1;
b[trees[i][0]][trees[i][3]] = 1;
}
build(b);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0;i < v[x].size();i++){
| ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0;i < p.size();i++){
| ~~^~~~~~~~~~
supertrees.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j = 0;j < p[i].size();j++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0;i < p.size();i++){
| ~~^~~~~~~~~~
supertrees.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int k = 0;k < p.size();k++){
| ~~^~~~~~~~~~
supertrees.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:60:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:69:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
| ~~^~~~~~~~~~
supertrees.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0;i < p.size();i++) b[i].resize(p.size(), 0);
| ~~^~~~~~~~~~
supertrees.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0;i < p.size();i++){
| ~~^~~~~~~~~~
supertrees.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j = 0;j < trees[i].size() - 1;j++){
| ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
| ~~^~~~~~~~~~
supertrees.cpp:91:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:93:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:102:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
| ~~^~~~~~~~~~
supertrees.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i = 0;i < p.size();i++){
| ~~^~~~~~~~~~
supertrees.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int j = 0;j < trees[i].size() - 1;j++){
| ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0;i < p.size();i++) {pa[i] = i;trees[i].clear();}
| ~~^~~~~~~~~~
supertrees.cpp:122:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:124:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:131:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int j = 0;j < graph[i].size();j++){
| ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:133:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int k = 0;k < v[x].size();k++){
| ~~^~~~~~~~~~~~~
supertrees.cpp:139:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i = 0;i < p.size();i++) trees[find(i)].push_back(i);
| ~~^~~~~~~~~~
supertrees.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i = 0;i < p.size();i++){
| ~~^~~~~~~~~~
supertrees.cpp:144:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int j = 0;j < trees[i].size() - 1;j++){
| ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:152:5: error: 'build' was not declared in this scope
152 | build(b);
| ^~~~~