#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
using ld = long double;
const int mxN = 1e3+10;
int p[mxN];
vector<int> adj[mxN];
int type[mxN];
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
void uni(int a, int b) {
a = get(a); b = get(b);
if(a == b) return ;
if(p[a] > p[b]) swap(a, b);
p[a] += p[b];
p[b] = a;
}
int construct(vector<vector<int>> P) {
int n = P.size();
for(int i = 0; i < n; i++) p[i] = -1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(P[i][j] == 1 && (get(i) != get(j))) {
uni(i, j);
adj[i].push_back(j);
adj[j].push_back(i);
type[i] = 1; type[j] = 1;
}
}
}
bool pos = true;
for(int i = 0; i < n; i++) {
vector<int> v;
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(P[i][j] == 2 && (get(j) != get(i))) v.push_back(j);
}
if(v.empty()) continue;
if(v.size() == 1) {
pos = false;
break;
}
int x = get(i);
for(int i = 0; i + 1 < v.size(); i++) {
adj[v[i]].push_back(v[i+1]);
adj[v[i+1]].push_back(v[i]);
uni(v[i], v[i+1]);
type[v[i]] = 2;
type[v[i+1]] = 2;
}
adj[x].push_back(v[0]);
adj[v[0]].push_back(x);
adj[v[v.size()-1]].push_back(x);
adj[x].push_back(v[v.size()-1]);
uni(x, v[0]);
}
if(!pos) return 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(P[i][j]) {
if(get(i) != get(j)) pos = false;
else {
if(P[i][j] == 1) {
if(type[i] != 1 || type[j] != 1) pos = false;
}
else {
if(type[i] == 1 && type[j] == 1) pos = false;
}
}
}
else {
if(get(i) == get(j)) pos = false;
}
}
}
for(int i = 0; i < n; i++) {
cout << type[i] << '\n';
}
//if(!pos) return 0;
vector<vector<int>> ans(n, vector<int>(n));
for(int i = 0; i < n; i++) {
for(auto it : adj[i]) {
ans[i][it] = ans[it][i] = 1;
}
}
build(ans);
return 1;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<vector<int>> a = {{1, 1, 1, 1, 1, 1, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 2, 2, 2},
{2, 2, 2, 2, 2, 2, 1, 2, 2},
{2, 2, 2, 2, 2, 2, 2, 1, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 1}};
cout << construct(a);
}*/
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i + 1 < v.size(); i++) {
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
