// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename F, typename S> ostream& operator<<(ostream& os, const pair<F, S> &p) { return os<<"("<<p.first<<", "<<p.second<<")"; }
template<typename T> ostream &operator<<(ostream & os, const vector<T> &v) { os << "{"; typename vector< T > :: const_iterator it;
for( it = v.begin(); it != v.end(); it++ ) { if( it != v.begin() ) os << ", "; os << *it; } return os << "}"; }
void dbg_out() { cerr<<'\n'; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr<<' '<<H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr<<"(" << #__VA_ARGS__ <<"):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct DSU {
vi dsu, siz;
DSU(int n) : dsu(n), siz(n, 1) {
iota(all(dsu), 0);
}
int find(int x) {
if(dsu[x] == x) return x;
return dsu[x] = find(dsu[x]);
}
void merge(int a, int b) {
a = find(a); b = find(b);
if(a == b) return;
if(siz[a] < siz[b]) swap(a, b);
else if(siz[a] == siz[b]) siz[a]++;
dsu[b] = a;
}
bool same(int a, int b) {
return find(a) == find(b);
}
};
int n;
vector<vi> answer;
pair<bool, vi> find_connected(vector<vi> &p) {
DSU dsu(n);
rep(i,0,n) rep(j,0,n)
if(p[i][j] > 0) dsu.merge(i, j);
rep(i,0,n) rep(j,0,n)
if(p[i][j] == 0 && dsu.same(i, j))
return {false, {}};
return {true, dsu.dsu};
}
pair<bool, vi> find_one_connected(vector<vi> &p) {
DSU dsu(n);
rep(i,0,n) rep(j,0,n)
if(p[i][j] == 1) dsu.merge(i, j);
rep(i,0,n) rep(j,0,n)
if(p[i][j] != 1 && dsu.same(i, j))
return {false, {}};
return {true, dsu.dsu};
}
int construct(vector<vi> p) {
n = p.size();
answer.assign(n, vi(n, 0));
auto [correct, conn] = find_connected(p);
if(!correct) return 0;
auto [one_correct, one_conn] = find_one_connected(p);
if(!one_correct) return 0;
rep(i,0,n) {
if(one_conn[i] == i) continue;
answer[i][one_conn[i]] = 1;
answer[one_conn[i]][i] = 1;
}
vector<vi> cycles(n);
rep(i,0,n) if(one_conn[i] == i)
cycles[conn[i]].push_back(i);
rep(i,0,n)
rep(j,1,sz(cycles[i])) {
answer[cycles[i][j]][cycles[i][j-1]] = true;
answer[cycles[i][j-1]][cycles[i][j]] = true;
}
build(answer);
return 1;
}
Compilation message
plants.cpp:3:10: fatal error: supertrees.h: No such file or directory
3 | #include "supertrees.h"
| ^~~~~~~~~~~~~~
compilation terminated.
