#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class UnionFind{
public:
UnionFind(ll S){
p.resize(S + 5, -1);
}
ll Find(ll n){
if (p[n] < 0) return n;
else return p[n] = Find(p[n]);
}
void Union(ll a, ll b){
a = Find(a), b = Find(b);
if (a == b) return;
p[a] += p[b];
p[b] = a;
}
bool Same(ll a, ll b) { return Find(a) == Find(b); }
ll Size(ll n) { return -p[Find(n)]; }
bool Root(ll n) {return n == Find(n);}
private:
vector<ll> p;
};
ll N;
ll P[1005][1005];
vector<ll> A;
int construct(std::vector<std::vector<int>> P) {
N = P.size();
vector<vector<int>> T(N, vector<int>(N));
auto add_edge = [&](ll u, ll v) -> void{
T[u][v] = T[v][u] = 1;
};
UnionFind S1(N), S2(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(P[i][j] == 3){
return 0;
}
if(j >= i || P[i][j] == 0) continue;
S1.Union(i, j);
if(P[i][j] == 1){
S2.Union(i, j);
}
}
}
for(int i = 0; i < N; i++){
if(!S2.Root(i)){
add_edge(S2.Find(i), i);
}
}
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
if(S2.Same(i, j) && P[i][j] != 1){
return 0;
} else if(S1.Same(i, j) && P[i][j] != 2 && P[i][j] != 1){
return 0;
}
}
}
for(int i = 0; i < N; i++){
if(!S1.Root(i)) continue;
A.clear();
for(int j = 1; j <= N; j++){
if(S1.Same(i, j) && S2.Root(j)){
A.push_back(j);
}
}
if(A.size() == 2) return 0;
if(A.size() == 1) continue;
for(int j = 0; j < A.size(); j++){
add_edge(A[j], A[(j == A.size() - 1 ? 0 : j + 1)]);
}
}
build(T);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j = 0; j < A.size(); j++){
| ~~^~~~~~~~~~
supertrees.cpp:75:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | add_edge(A[j], A[(j == A.size() - 1 ? 0 : j + 1)]);
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
7 ms |
1200 KB |
Output is correct |
7 |
Correct |
181 ms |
23924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
7 ms |
1200 KB |
Output is correct |
7 |
Correct |
181 ms |
23924 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1208 KB |
Output is correct |
13 |
Correct |
170 ms |
23924 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
812 KB |
Output is correct |
17 |
Correct |
88 ms |
14080 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
45 ms |
6264 KB |
Output is correct |
21 |
Correct |
172 ms |
23932 KB |
Output is correct |
22 |
Correct |
174 ms |
23924 KB |
Output is correct |
23 |
Correct |
185 ms |
23928 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
70 ms |
14020 KB |
Output is correct |
26 |
Correct |
70 ms |
14024 KB |
Output is correct |
27 |
Correct |
185 ms |
24052 KB |
Output is correct |
28 |
Correct |
170 ms |
23932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
7 ms |
1200 KB |
Output is correct |
7 |
Correct |
181 ms |
23924 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1208 KB |
Output is correct |
13 |
Correct |
170 ms |
23924 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
812 KB |
Output is correct |
17 |
Correct |
88 ms |
14080 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
45 ms |
6264 KB |
Output is correct |
21 |
Correct |
172 ms |
23932 KB |
Output is correct |
22 |
Correct |
174 ms |
23924 KB |
Output is correct |
23 |
Correct |
185 ms |
23928 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
70 ms |
14020 KB |
Output is correct |
26 |
Correct |
70 ms |
14024 KB |
Output is correct |
27 |
Correct |
185 ms |
24052 KB |
Output is correct |
28 |
Correct |
170 ms |
23932 KB |
Output is correct |
29 |
Correct |
0 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
7 ms |
1200 KB |
Output is correct |
7 |
Correct |
181 ms |
23924 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1208 KB |
Output is correct |
13 |
Correct |
170 ms |
23924 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
812 KB |
Output is correct |
17 |
Correct |
88 ms |
14080 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
45 ms |
6264 KB |
Output is correct |
21 |
Correct |
172 ms |
23932 KB |
Output is correct |
22 |
Correct |
174 ms |
23924 KB |
Output is correct |
23 |
Correct |
185 ms |
23928 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
70 ms |
14020 KB |
Output is correct |
26 |
Correct |
70 ms |
14024 KB |
Output is correct |
27 |
Correct |
185 ms |
24052 KB |
Output is correct |
28 |
Correct |
170 ms |
23932 KB |
Output is correct |
29 |
Correct |
0 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |