#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
void build(vvi b);
class Solver{
private:
vvi p;
ll n;
vvi ans;
vi hasSet;
bool add_edge(ll u, ll v){
if (ans[u][v] || u == v) return 0;
ans[u][v] = ans[v][u] = 1;
return 1;
}
vi concat(const vi& v1, const vi& v2, const vi& v3){
vi res;
for (ll i = v1.size()-1; i >= 0; i--) res.push_back(v1[i]);
for (auto i: v2) res.push_back(i);
for (auto i: v3) res.push_back(i);
return res;
}
bool processGroup(const vi& cur_set){
// check if all are connected to each other
for (auto j: cur_set){
for (auto k: cur_set){
if (j == k) continue;
if (p[j][k] == 0) return 0;
}
}
vi two_set; vvi one_set(2,vi());
vi hasCurSet(n,0);
for (auto j: cur_set){
if (hasCurSet[j]) continue;
hasCurSet[j] = true;
bool hasOne = false;
for (auto k: cur_set){
if (k != j && p[j][k] == 1) hasOne = true;
}
if (hasOne){
ll cur_one = 0;
for (ll k = 0; 2 > k; k++){
if (one_set[k].size()) cur_one++;
}
if (cur_one == 2) return 0;
one_set[cur_one].push_back(j);
for (auto k: cur_set){
if (p[j][k] == 1 && j != k){
one_set[cur_one].push_back(k);
if (hasCurSet[k]) return 0;
hasCurSet[k] = true;
}
}
}else{
two_set.push_back(j);
}
}
/*
cout << "one_set:\n";
for (auto j: one_set){
for (auto k: j) cout << k << " ";
cout << endl;
}
cout << "two_set:\n";
for (auto j: two_set) cout << j << " ";
cout << endl;
*/
vi nodes = concat(one_set[0],two_set,one_set[1]);
for (ll j = 0; nodes.size() > j+1; j++){
add_edge(nodes[j],nodes[j+1]);
//cout << nodes[j] << " " << nodes[j+1] << endl;
}
if (two_set.size()){
ii extra_edge = ii(two_set[0],two_set[two_set.size()-1]);
if (one_set[0].size()) extra_edge.F = one_set[0][0];
if (one_set[1].size()) extra_edge.S = one_set[1][0];
bool b = add_edge(extra_edge.F, extra_edge.S);
//cout << extra_edge.F << " " << extra_edge.S << endl;
if (!b) return 0;
}
for (auto i: cur_set){
for (auto j: cur_set){
if (j != i) p[i][j] = 0;
}
}
return 1;
}
public:
Solver(vvi p): p(p),n(p.size()),ans(n,vi(n,0)), hasSet(n,0){
}
bool solve(){
for (int i = 0; n > i; i++){
if (hasSet[i]){
for (ll j = 0; n > j; j++){
if (p[i][j] && j != i) return 0;
}
continue;
}
vi cur_set;
for (ll j = 0; n > j; j++){
if (p[i][j] != 0){
cur_set.push_back(j);
if (hasSet[j]) return 0;
else hasSet[j] = 1;
}
}
bool res = processGroup(cur_set);
if (!res) return 0;
}
for (ll i = 0; n > i; i++){
for (ll j = 0; n > j; j++){
//if (p[i][j] && i != j) return 0;
}
}
build(ans);
return 1;
}
};
int construct(vvi p) {
Solver mySolver(p);
return mySolver.solve();
}
Compilation message
supertrees.cpp: In member function 'bool Solver::processGroup(const vi&)':
supertrees.cpp:84:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
84 | for (ll j = 0; nodes.size() > j+1; j++){
| ~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
