#ifdef LOCAL
#else
#include "supertrees.h"
#endif
#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...); }
#ifdef LOCAL
bool build(vector<vector<int>> p) {
return true;
}
#else
#endif
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;
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);
}
}
for (auto row: res) cout << row << '\n';
build(res);
return 1;
}
#ifdef LOCAL
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];
}
}
construct(p);
return 0;
}
#else
#endif
Compilation message
supertrees.cpp: In lambda function:
supertrees.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < v.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
80 | if (overall[0] || overall[2] && overall[3]) {
supertrees.cpp:131:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int j = 0; j < other.size(); j++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:155:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for (int j = 0; j < other.size(); j++) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:60:13: warning: unused variable 'sz' [-Wunused-variable]
60 | int sz = comp.size();
| ^~
| # |
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 |
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 |
0 ms |
256 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 |
0 ms |
256 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
