#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
//bool build(vector<vector<int>> p) {
// return true;
//}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> res(n, vector<int>(n, 0));
vector<bool> vis(n);
auto ae = [&](int u, int v) {
res[u][v] = 1;
res[v][u] = 1;
};
auto make_cycle = [&](vector<int>& v) {
for (int i = 0; i < v.size(); i++) {
ae(v[i], v[(i + 1) % v.size()]);
}
};
auto make_triple = [&](vector<int>& v) {
make_cycle(v);
ae(v[0], v[1]);
};
auto make_chain = [&](vector<int>& v) {
for (int i = 0; i < v.size() - 1; i++) {
ae(v[i], v[i + 1]);
}
};
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vector<int> comp;
function<void(int)> dfs_comp = [&](int src) {
vis[src] = true;
comp.push_back(src);
for (int nxt = 0; nxt < n; nxt++) {
if (p[src][nxt] == 0 || vis[nxt]) continue;
dfs_comp(nxt);
}
};
dfs_comp(i);
int sz = comp.size();
vector<int> overall(4);
vector<int> one;
vector<int> other;
cout << comp;
for (int x: comp) {
vector<int> cnt(4);
for (int y: comp) {
if (x == y) continue;
cnt[p[x][y]]++;
overall[p[x][y]]++;
}
if (cnt[0]) {
return 0;
}
if (cnt[1] == 0) {
other.push_back(x);
} else {
one.push_back(x);
}
}
if (overall[0] || overall[2] && overall[3]) {
return 0;
}
vector<int> le;
vector<int> ri;
for (int x: one) {
bool ok = false;
for (int y: le) {
if (p[x][y] != 1) {
ri.push_back(x);
ok = true;
break;
}
}
if (ok == false) {
le.push_back(x);
}
}
for (int x: le) {
for (int y: le) {
if (x == y) continue;
if (p[x][y] != 1) {
return 0;
}
}
}
for (int x: ri) {
for (int y: ri) {
if (x == y) continue;
if (p[x][y] != 1) {
return 0;
}
}
}
for (int x: le) {
for (int y: ri) {
if (overall[2] && p[x][y] != 2) {
return 0;
}
if (overall[3] && p[x][y] != 3) {
return 0;
}
}
}
int cycle = (le.size() ? 1 : 0) + (ri.size() ? 1 : 0) + other.size();
if (overall[2]) {
if (cycle < 3) {
return 0;
}
if (le.size() == 0 && ri.size() == 0) {
make_cycle(other);
for (int j = 0; j < other.size(); j++) {
ae(other[j], other[(j + 1) % other.size()]);
}
} else if (le.size() == 0) {
other.push_back(ri[0]);
make_cycle(other);
make_chain(ri);
} else if (ri.size() == 0) {
other.push_back(le[0]);
make_cycle(other);
make_chain(le);
} else {
other.push_back(le[0]);
other.push_back(ri[0]);
make_cycle(other);
make_chain(le);
make_chain(ri);
}
} else if (overall[3]) {
if (cycle < 4) {
return 0;
}
if (le.size() == 0 && ri.size() == 0) {
make_triple(other);
for (int j = 0; j < other.size(); j++) {
ae(other[j], other[(j + 1) % other.size()]);
}
} else if (le.size() == 0) {
other.push_back(ri[0]);
make_triple(other);
make_chain(ri);
} else if (ri.size() == 0) {
other.push_back(le[0]);
make_triple(other);
make_chain(le);
} else {
other.push_back(le[0]);
other.push_back(ri[0]);
make_triple(other);
make_chain(le);
make_chain(ri);
}
} else {
vector<int> big;
for (int x: one) big.push_back(x);
for (int x: other) big.push_back(x);
make_chain(big);
}
}
build(res);
return 1;
}
//int main() {
// int n; cin >> n;
// vector<vector<int>> p(n, vector<int>(n, 0));
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cin >> p[i][j];
// }
// }
// return 0;
//}
Compilation message
supertrees.cpp: In lambda function:
supertrees.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < v.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:75:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
75 | if (overall[0] || overall[2] && overall[3]) {
supertrees.cpp:126:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int j = 0; j < other.size(); j++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:150:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int j = 0; j < other.size(); j++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:54:13: warning: unused variable 'sz' [-Wunused-variable]
54 | int sz = comp.size();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
