// Source:https://ioinformatics.org/files/ioi2020problem2.pdf
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
vector<vi> pth;
vector<vi> sol;
int n;
vector<bool> vis;
bool works=true;
vector<vi> p;
void solve(vi here) {
vi cyc;
vi ncyc;
for (auto i: here) {
bool fail=true;
for (auto j: here) {
if (i != j && p[i][j] != 2) {
fail=false;
}
}
if (!fail) ncyc.pb(i);
else cyc.pb(i);
}
for (auto i: ncyc) {
for (auto j: ncyc) {
if (p[i][j] != 1) works=false;
// cout << i << j << p[i][j] << endl;
}
}
int chosen;
if (ncyc.size()) {
chosen = ncyc.back();
ncyc.pop_back();
}
FOR(i, 0, cyc.size() - 1) {
sol[cyc[i]][cyc[i + 1]] = 1;
sol[cyc[i + 1]][cyc[i]] = 1;
}
if (cyc.size() && ncyc.size()) {
sol[chosen][cyc[0]]=1;
sol[cyc[0]][chosen]=1;
sol[chosen][cyc[cyc.size() - 1]]=1;
sol[cyc[cyc.size() - 1]][chosen]=1;
}
if (ncyc.size()) {
sol[ncyc[0]][chosen] = 1;
sol[chosen][ncyc[0]] = 1;
FOR(i, 0, ncyc.size() - 1) {
sol[ncyc[i]][ncyc[i + 1]] = 1;
sol[ncyc[i + 1]][ncyc[i]] = 1;
}
}
}
// void build(vector<vi> t) {
// for (auto val: t) {
// for (auto j: val) {
// cout << j << ' ';
// }
// cout << endl;
// }
// }
int construct(vector<vi> P) {
n = P.size();
p = P;
sol = vector<vi>(n, vi(n, 0));
vis.resize(n);
FOR(i, 0, n) {
if (!vis[i]) {
vi here;
FOR(j, 0, n) {
if (p[i][j]) {
vis[j]=true;
here.pb(j);
}
}
// cout << i << endl;
solve(here);
}
}
if (!works) return 0;
build(sol);
return 1;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// // cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}}) << endl;
// cout << construct({{1, 0}, {0, 1}}) << endl;
// }
Compilation message
supertrees.cpp: In function 'void solve(vi)':
supertrees.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
62 | FOR(i, 0, cyc.size() - 1) {
| ~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:62:2: note: in expansion of macro 'FOR'
62 | FOR(i, 0, cyc.size() - 1) {
| ^~~
supertrees.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
78 | FOR(i, 0, ncyc.size() - 1) {
| ~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:78:3: note: in expansion of macro 'FOR'
78 | FOR(i, 0, ncyc.size() - 1) {
| ^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:115:2: error: 'build' was not declared in this scope
115 | build(sol);
| ^~~~~
