#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector < int > pr, rk;
int N;
dsu(){}
dsu(int n):N(n){
pr.resize(N), rk.resize(N);
for(int i = 0; i < N; ++i) pr[i] = i, rk[i] = 1;
}
inline int get(int x){
return x == pr[x] ? x : pr[x] = get(pr[x]);
}
inline bool unite(int x, int y){
x = get(x), y = get(y);
if(x != y){
if(rk[x] < rk[y]) swap(x, y);
pr[y] = x, rk[x] += rk[y];
return true;
}
return false;
}
}all(1004), one(1004);
vector < int > circle[1004], line[1004];
int construct(std::vector<std::vector<int>> p) {
int N = p.size();
std::vector<std::vector<int>> answer;
answer.resize(N);
for(int i = 0; i < N; ++i){
answer[i].resize(N);
for(int j = 0; j < N; ++j){
if(p[i][j] == 3){
return 0;
}
if(p[i][j]){
all.unite(i, j);
}
if(p[i][j] == 1){
one.unite(i, j);
}
}
}
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
if(!p[i][j] && all.get(i) == all.get(j)) return 0;
if(p[i][j] == 2 && one.get(i) == one.get(j)) return 0;
}
}
for(int i = 0; i < N; ++i){
if(one.get(i) == i){
circle[all.get(i)].push_back(i);
}
line[one.get(i)].push_back(i);
}
for(int i = 0; i < N; ++i){
for(int j = 0; j < (int)circle[i].size() - 1; ++j){
answer[circle[i][j]][circle[i][j + 1]] = answer[circle[i][j + 1]][circle[i][j]] = 1;
}
if((int)circle[i].size() >= 3){
answer[circle[i][0]][circle[i].back()] = answer[circle[i].back()][circle[i][0]] = 1;
}
for(int j = 0; j < (int)line[i].size() - 1; ++j){
answer[line[i][j]][line[i][j + 1]] = answer[line[i][j + 1]][line[i][j]] = 1;
}
}
build(answer);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1280 KB |
Output is correct |
7 |
Correct |
264 ms |
22268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1280 KB |
Output is correct |
7 |
Correct |
264 ms |
22268 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
360 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
14 ms |
1280 KB |
Output is correct |
13 |
Correct |
273 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
125 ms |
12308 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
66 ms |
5880 KB |
Output is correct |
21 |
Correct |
250 ms |
22264 KB |
Output is correct |
22 |
Correct |
247 ms |
22160 KB |
Output is correct |
23 |
Correct |
270 ms |
22136 KB |
Output is correct |
24 |
Correct |
246 ms |
22296 KB |
Output is correct |
25 |
Correct |
108 ms |
12280 KB |
Output is correct |
26 |
Correct |
106 ms |
12152 KB |
Output is correct |
27 |
Correct |
274 ms |
22136 KB |
Output is correct |
28 |
Correct |
245 ms |
22136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
1 ms |
384 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 |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
67 ms |
5880 KB |
Output is correct |
5 |
Correct |
257 ms |
22264 KB |
Output is correct |
6 |
Correct |
252 ms |
22140 KB |
Output is correct |
7 |
Correct |
270 ms |
22136 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
63 ms |
6008 KB |
Output is correct |
10 |
Correct |
250 ms |
22136 KB |
Output is correct |
11 |
Correct |
255 ms |
22168 KB |
Output is correct |
12 |
Correct |
263 ms |
22136 KB |
Output is correct |
13 |
Correct |
1 ms |
512 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
62 ms |
5880 KB |
Output is correct |
17 |
Correct |
254 ms |
22392 KB |
Output is correct |
18 |
Correct |
254 ms |
22264 KB |
Output is correct |
19 |
Correct |
255 ms |
22264 KB |
Output is correct |
20 |
Correct |
247 ms |
22264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1280 KB |
Output is correct |
7 |
Correct |
264 ms |
22268 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
360 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
14 ms |
1280 KB |
Output is correct |
13 |
Correct |
273 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
125 ms |
12308 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
66 ms |
5880 KB |
Output is correct |
21 |
Correct |
250 ms |
22264 KB |
Output is correct |
22 |
Correct |
247 ms |
22160 KB |
Output is correct |
23 |
Correct |
270 ms |
22136 KB |
Output is correct |
24 |
Correct |
246 ms |
22296 KB |
Output is correct |
25 |
Correct |
108 ms |
12280 KB |
Output is correct |
26 |
Correct |
106 ms |
12152 KB |
Output is correct |
27 |
Correct |
274 ms |
22136 KB |
Output is correct |
28 |
Correct |
245 ms |
22136 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Incorrect |
1 ms |
384 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 |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1280 KB |
Output is correct |
7 |
Correct |
264 ms |
22268 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
360 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
14 ms |
1280 KB |
Output is correct |
13 |
Correct |
273 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
896 KB |
Output is correct |
17 |
Correct |
125 ms |
12308 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
66 ms |
5880 KB |
Output is correct |
21 |
Correct |
250 ms |
22264 KB |
Output is correct |
22 |
Correct |
247 ms |
22160 KB |
Output is correct |
23 |
Correct |
270 ms |
22136 KB |
Output is correct |
24 |
Correct |
246 ms |
22296 KB |
Output is correct |
25 |
Correct |
108 ms |
12280 KB |
Output is correct |
26 |
Correct |
106 ms |
12152 KB |
Output is correct |
27 |
Correct |
274 ms |
22136 KB |
Output is correct |
28 |
Correct |
245 ms |
22136 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Incorrect |
1 ms |
384 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |