#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
vector<vector<int>> p, ans;
vector<int>idk, comp;
int n, rep[1002], selected, viz[1002];
void dfs1 (int nod) {
rep[nod] = selected;
viz[nod] = 1;
for (int i = 0; i < n; i++)
if (p[nod][i] == 1 && !viz[i])
dfs1(i);
}
void dfs2 (int nod) {
comp.push_back(nod);
viz[nod] = 1;
for (auto it : idk)
if (!viz[it] && p[nod][it] == 2)
dfs2(it);
}
int construct (vector<vector<int>>aux) {
p = aux;
n = p.size();
ans.resize(n);
for (int i = 0; i < n; i++)
ans[i].resize(n);
for (int i = 0; i < n; i++)
if (!viz[i]) {
selected = i;
idk.push_back(selected);
dfs1(i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (rep[i] == rep[j] && p[i][j] != 1)
return 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (rep[i] != rep[j] && p[i][j] != p[rep[i]][rep[j]])
return 0;
for (auto it : idk) {
int aux = 0;
for (int j = 0; j < n; j++)
if (rep[j] == it) {
if (aux)
ans[aux][j] = ans[j][aux] = 1;
aux = j;
}
}
memset(viz, 0, sizeof(viz));
for (auto it : idk) {
if (!viz[it]) {
comp.clear();
dfs2(it);
if (comp.size() == 1)
continue;
if (comp.size() == 2)
return 0;
for (int i = 0; i < comp.size(); i++)
ans[comp[i]][comp[(i + 1) % comp.size()]] = ans[comp[(i + 1) % comp.size()]][comp[i]] = 1;
}
}
build(ans);
return 1;
}
// int main ()
// {
// cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
// return 0;
// }
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
9 ms |
1364 KB |
Output is correct |
9 |
Correct |
174 ms |
27912 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
13 ms |
1440 KB |
Output is correct |
13 |
Correct |
226 ms |
27976 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
43 ms |
7176 KB |
Too few ways to get from 0 to 5, should be 1 found 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
3 |
Halted |
0 ms |
0 KB |
- |