#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct DisjointSetUnion {
int n;
vector<int> par;
vector<int> sz;
DisjointSetUnion(int n) {
par.resize(n);
sz.assign(n, 1);
iota(par.begin(), par.end(), 0);
}
int find(int x) {
return par[x] = (x == par[x] ? x : find(par[x]));
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
bool same(int u, int v) {
return (find(u) == find(v));
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
bool bad = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bad |= (p[i][j] == 3);
}
}
if (bad) return 0;
vector<vector<int>> b(n, vector<int> (n, 0));
DisjointSetUnion dsu(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1) {
dsu.unite(i, j);
}
}
}
vector<int> roots;
for (int i = 0; i < n; i++) {
if (dsu.par[i] == i) {
vector<int> nodes;
for (int j = 0; j < n; j++) {
if (dsu.par[j] == i) {
nodes.push_back(j);
}
}
for (int u : nodes) {
for (int v : nodes) {
bad |= (p[u][v] != 1);
}
}
roots.push_back(i);
for (int j = 1; j < (int) nodes.size(); j++) b[nodes[j]][nodes[j - 1]] = b[nodes[j - 1]][nodes[j]] = 1;
}
}
if (bad) return 0;
DisjointSetUnion rot(n);
for (int u : roots) {
for (int v : roots) {
if (p[u][v] == 2) {
rot.unite(u, v);
}
}
}
for (int u : roots) {
if (u == rot.par[u] && rot.sz[u] > 1) {
vector<int> nodes;
for (int v : roots) {
if (u == rot.par[v]) {
nodes.push_back(v);
}
}
for (int i : nodes) {
for (int j : nodes) {
if (i != j && p[i][j] != 2) bad = true;
}
}
int sz = nodes.size();
for (int i = 0; i < sz; i++) {
b[nodes[i]][nodes[(i + 1) % sz]] = b[nodes[(i + 1) % sz]][nodes[i]] = 1;
}
}
}
if (bad) return 0;
build(b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
10 ms |
1228 KB |
Output is correct |
7 |
Correct |
232 ms |
23920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
10 ms |
1228 KB |
Output is correct |
7 |
Correct |
232 ms |
23920 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
12 ms |
1228 KB |
Output is correct |
13 |
Correct |
226 ms |
23932 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
844 KB |
Output is correct |
17 |
Correct |
111 ms |
14068 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
57 ms |
6160 KB |
Output is correct |
21 |
Correct |
226 ms |
23932 KB |
Output is correct |
22 |
Correct |
221 ms |
23932 KB |
Output is correct |
23 |
Correct |
247 ms |
24004 KB |
Output is correct |
24 |
Correct |
252 ms |
24076 KB |
Output is correct |
25 |
Correct |
102 ms |
14072 KB |
Output is correct |
26 |
Correct |
95 ms |
14064 KB |
Output is correct |
27 |
Correct |
242 ms |
24004 KB |
Output is correct |
28 |
Correct |
232 ms |
24004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
56 ms |
6256 KB |
Output is correct |
5 |
Correct |
228 ms |
24132 KB |
Output is correct |
6 |
Correct |
226 ms |
24024 KB |
Output is correct |
7 |
Correct |
245 ms |
24176 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
57 ms |
6260 KB |
Output is correct |
10 |
Correct |
228 ms |
24012 KB |
Output is correct |
11 |
Correct |
228 ms |
24004 KB |
Output is correct |
12 |
Correct |
250 ms |
24004 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
288 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
58 ms |
6228 KB |
Output is correct |
17 |
Correct |
228 ms |
23932 KB |
Output is correct |
18 |
Correct |
227 ms |
23992 KB |
Output is correct |
19 |
Correct |
224 ms |
23932 KB |
Output is correct |
20 |
Correct |
233 ms |
23992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
10 ms |
1228 KB |
Output is correct |
7 |
Correct |
232 ms |
23920 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
12 ms |
1228 KB |
Output is correct |
13 |
Correct |
226 ms |
23932 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
844 KB |
Output is correct |
17 |
Correct |
111 ms |
14068 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
57 ms |
6160 KB |
Output is correct |
21 |
Correct |
226 ms |
23932 KB |
Output is correct |
22 |
Correct |
221 ms |
23932 KB |
Output is correct |
23 |
Correct |
247 ms |
24004 KB |
Output is correct |
24 |
Correct |
252 ms |
24076 KB |
Output is correct |
25 |
Correct |
102 ms |
14072 KB |
Output is correct |
26 |
Correct |
95 ms |
14064 KB |
Output is correct |
27 |
Correct |
242 ms |
24004 KB |
Output is correct |
28 |
Correct |
232 ms |
24004 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 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 |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
10 ms |
1228 KB |
Output is correct |
7 |
Correct |
232 ms |
23920 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
12 ms |
1228 KB |
Output is correct |
13 |
Correct |
226 ms |
23932 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
844 KB |
Output is correct |
17 |
Correct |
111 ms |
14068 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
57 ms |
6160 KB |
Output is correct |
21 |
Correct |
226 ms |
23932 KB |
Output is correct |
22 |
Correct |
221 ms |
23932 KB |
Output is correct |
23 |
Correct |
247 ms |
24004 KB |
Output is correct |
24 |
Correct |
252 ms |
24076 KB |
Output is correct |
25 |
Correct |
102 ms |
14072 KB |
Output is correct |
26 |
Correct |
95 ms |
14064 KB |
Output is correct |
27 |
Correct |
242 ms |
24004 KB |
Output is correct |
28 |
Correct |
232 ms |
24004 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 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 |
- |