#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;
void build(vector<vector<int>> _b);
const int MAXN = 1e3+100;
int p[MAXN], sz[MAXN];
void init(int n){
iota(p, p+n, 0);
fill(sz, sz+n, 1);
}
int find_parent(int x){
if(x == p[x])
return x;
return p[x] = find_parent(p[x]);
}
bool same_set(int a, int b){
return (find_parent(a) == find_parent(b));
}
void union_set(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
int p2[MAXN], sz2[MAXN];
void init2(int n){
iota(p2, p2+n, 0);
fill(sz2, sz2+n, 1);
}
int find2(int x){
if(x == p2[x])
return x;
return p2[x] = find2(p2[x]);
}
bool same2(int a, int b){
return (find2(a) == find2(b));
}
void union2(int a, int b){
a = find2(a);
b = find2(b);
if(a == b)
return;
if(sz2[a] < sz2[b])
swap(a, b);
p2[b] = a;
sz2[a] += sz2[b];
}
int construct(vector<vector<int>> p){
int N = SZ(p);
init(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(p[i][j] > 0){
union_set(i, j);
}
}
}
vector<vector<int>> ans(N, vector<int>(N, 0));
vector<bool> vis(N, false);
vector<bool> vis2(N, false), vis3(N, false);
init2(N);
for(int i = 0; i < N; i++){
int v = find_parent(i);
if(!vis[v]){
vis[v] = true;
vector<int> vertici;
vertici.pb(i);
for(int j = i+1; j < N; j++){
if(same_set(i, j)){
vertici.pb(j);
}
}
for(int j = 0; j < SZ(vertici); j++){
for(int k = 0; k < SZ(vertici); k++){
if(p[vertici[j]][vertici[k]] == 0){
return 0;
}
}
}
if(SZ(vertici) == 2 && p[vertici[0]][vertici[1]] >= 2){
return 0;
}
bool onlyone = true;
for(int j = 0; j < SZ(vertici); j++){
for(int k = 0; k < SZ(vertici); k++){
if(p[vertici[j]][vertici[k]] != 1){
onlyone = false;
}
}
}
if(onlyone){
for(int j = 1; j < SZ(vertici); j++){
ans[vertici[j-1]][vertici[j]] = 1;
ans[vertici[j]][vertici[j-1]] = 1;
}
continue;
}
for(int j = 0; j < SZ(vertici); j++){
for(int k = j + 1; k < SZ(vertici); k++){
int v1 = vertici[j], v2 = vertici[k];
if(p[v1][v2] == 1){
union2(v1, v2);
vis3[find2(v1)] = true;
}
}
}
vector<set<int>> vs;
for(int j = 0; j < SZ(vertici); j++){
int root = find2(vertici[j]);
if(vis2[root] || !vis3[root]) continue;
vis2[root] = true;
set<int> nuovo;
nuovo.insert(vertici[j]);
for(int k = j+1; k < SZ(vertici); k++){
if(same2(vertici[j], vertici[k])){
nuovo.insert(vertici[k]);
}
}
vs.pb(nuovo);
}
set<int> c;
for(auto x : vertici){
int root = find2(x);
if(!vis2[root]){
c.insert(x);
}
}
if(!SZ(vs)){
if(SZ(c) < 3) return 0;
int last = -1;
for(auto x : c){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
ans[*c.begin()][*c.rbegin()] = ans[*c.rbegin()][*c.begin()] = 1;
continue;
}
if(!SZ(c)){
if(SZ(vs) < 3)
return 0;
for(int ind = 0; ind < SZ(vs); ind++){
int j = (ind - 1 + SZ(vs)) % (SZ(vs));
int da = *vs[j].rbegin(), a = *vs[ind].begin();
ans[da][a] = ans[a][da] = 1;
int last = -1;
for(auto x : vs[ind]){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
}
continue;
}
if(SZ(c) == 1){
if(SZ(vs) < 2) return 0;
for(int ind = 0; ind < SZ(vs); ind++){
int last = -1;
for(auto x : vs[ind]){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
ans[*c.begin()][last] = ans[last][*c.begin()] = 1;
}
int v1 = *vs[0].rbegin(), v2 = *vs[1].rbegin();
ans[v1][v2] = ans[v2][v1] = 1;
continue;
}
if(SZ(c) > 1){
for(int ind = 0; ind < SZ(vs); ind++){
int last = -1;
for(auto x : vs[ind]){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
ans[last][*c.begin()] = ans[*c.begin()][last] = 1;
}
int last = -1;
for(auto x : c){
if(last != -1){
ans[last][x] = ans[x][last] = 1;
}
last = x;
}
ans[*c.rbegin()][*vs[0].rbegin()] = ans[*vs[0].rbegin()][*c.rbegin()] = 1;
continue;
}
}
}
build(ans);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1280 KB |
Output is correct |
7 |
Correct |
252 ms |
22140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1280 KB |
Output is correct |
7 |
Correct |
252 ms |
22140 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
241 ms |
22072 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
768 KB |
Output is correct |
17 |
Correct |
115 ms |
12120 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
62 ms |
5880 KB |
Output is correct |
21 |
Correct |
243 ms |
22136 KB |
Output is correct |
22 |
Correct |
238 ms |
22264 KB |
Output is correct |
23 |
Correct |
260 ms |
22264 KB |
Output is correct |
24 |
Correct |
242 ms |
22136 KB |
Output is correct |
25 |
Correct |
101 ms |
12152 KB |
Output is correct |
26 |
Correct |
97 ms |
12152 KB |
Output is correct |
27 |
Correct |
260 ms |
22136 KB |
Output is correct |
28 |
Correct |
243 ms |
22136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
10 ms |
1280 KB |
Output is correct |
9 |
Correct |
240 ms |
22136 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
11 ms |
1280 KB |
Output is correct |
13 |
Correct |
255 ms |
22136 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
768 KB |
Output is correct |
17 |
Correct |
114 ms |
12120 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
384 KB |
Output is correct |
21 |
Correct |
60 ms |
5880 KB |
Output is correct |
22 |
Correct |
241 ms |
22120 KB |
Output is correct |
23 |
Correct |
243 ms |
22136 KB |
Output is correct |
24 |
Correct |
259 ms |
22264 KB |
Output is correct |
25 |
Correct |
96 ms |
12152 KB |
Output is correct |
26 |
Correct |
97 ms |
12152 KB |
Output is correct |
27 |
Correct |
240 ms |
22136 KB |
Output is correct |
28 |
Correct |
262 ms |
22136 KB |
Output is correct |
29 |
Correct |
96 ms |
12152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
61 ms |
5880 KB |
Output is correct |
5 |
Correct |
245 ms |
22136 KB |
Output is correct |
6 |
Correct |
236 ms |
22136 KB |
Output is correct |
7 |
Correct |
261 ms |
22136 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
60 ms |
5880 KB |
Output is correct |
10 |
Correct |
246 ms |
22104 KB |
Output is correct |
11 |
Correct |
245 ms |
22304 KB |
Output is correct |
12 |
Correct |
258 ms |
22120 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Incorrect |
60 ms |
5880 KB |
Too many ways to get from 0 to 338, should be 1 found no less than 2 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1280 KB |
Output is correct |
7 |
Correct |
252 ms |
22140 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
241 ms |
22072 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
768 KB |
Output is correct |
17 |
Correct |
115 ms |
12120 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
62 ms |
5880 KB |
Output is correct |
21 |
Correct |
243 ms |
22136 KB |
Output is correct |
22 |
Correct |
238 ms |
22264 KB |
Output is correct |
23 |
Correct |
260 ms |
22264 KB |
Output is correct |
24 |
Correct |
242 ms |
22136 KB |
Output is correct |
25 |
Correct |
101 ms |
12152 KB |
Output is correct |
26 |
Correct |
97 ms |
12152 KB |
Output is correct |
27 |
Correct |
260 ms |
22136 KB |
Output is correct |
28 |
Correct |
243 ms |
22136 KB |
Output is correct |
29 |
Correct |
0 ms |
384 KB |
Output is correct |
30 |
Correct |
0 ms |
384 KB |
Output is correct |
31 |
Correct |
0 ms |
256 KB |
Output is correct |
32 |
Correct |
0 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
0 ms |
384 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
240 ms |
22136 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
0 ms |
384 KB |
Output is correct |
40 |
Correct |
11 ms |
1280 KB |
Output is correct |
41 |
Correct |
255 ms |
22136 KB |
Output is correct |
42 |
Correct |
0 ms |
256 KB |
Output is correct |
43 |
Correct |
0 ms |
256 KB |
Output is correct |
44 |
Correct |
5 ms |
768 KB |
Output is correct |
45 |
Correct |
114 ms |
12120 KB |
Output is correct |
46 |
Correct |
0 ms |
256 KB |
Output is correct |
47 |
Correct |
0 ms |
256 KB |
Output is correct |
48 |
Correct |
0 ms |
384 KB |
Output is correct |
49 |
Correct |
60 ms |
5880 KB |
Output is correct |
50 |
Correct |
241 ms |
22120 KB |
Output is correct |
51 |
Correct |
243 ms |
22136 KB |
Output is correct |
52 |
Correct |
259 ms |
22264 KB |
Output is correct |
53 |
Correct |
96 ms |
12152 KB |
Output is correct |
54 |
Correct |
97 ms |
12152 KB |
Output is correct |
55 |
Correct |
240 ms |
22136 KB |
Output is correct |
56 |
Correct |
262 ms |
22136 KB |
Output is correct |
57 |
Correct |
96 ms |
12152 KB |
Output is correct |
58 |
Correct |
0 ms |
288 KB |
Output is correct |
59 |
Correct |
1 ms |
256 KB |
Output is correct |
60 |
Correct |
5 ms |
768 KB |
Output is correct |
61 |
Correct |
114 ms |
12152 KB |
Output is correct |
62 |
Correct |
1 ms |
384 KB |
Output is correct |
63 |
Correct |
0 ms |
384 KB |
Output is correct |
64 |
Correct |
0 ms |
384 KB |
Output is correct |
65 |
Incorrect |
61 ms |
5880 KB |
Too many ways to get from 46 to 391, should be 1 found no less than 2 |
66 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
11 ms |
1280 KB |
Output is correct |
7 |
Correct |
252 ms |
22140 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
241 ms |
22072 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
768 KB |
Output is correct |
17 |
Correct |
115 ms |
12120 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
62 ms |
5880 KB |
Output is correct |
21 |
Correct |
243 ms |
22136 KB |
Output is correct |
22 |
Correct |
238 ms |
22264 KB |
Output is correct |
23 |
Correct |
260 ms |
22264 KB |
Output is correct |
24 |
Correct |
242 ms |
22136 KB |
Output is correct |
25 |
Correct |
101 ms |
12152 KB |
Output is correct |
26 |
Correct |
97 ms |
12152 KB |
Output is correct |
27 |
Correct |
260 ms |
22136 KB |
Output is correct |
28 |
Correct |
243 ms |
22136 KB |
Output is correct |
29 |
Correct |
0 ms |
384 KB |
Output is correct |
30 |
Correct |
0 ms |
384 KB |
Output is correct |
31 |
Correct |
0 ms |
256 KB |
Output is correct |
32 |
Correct |
0 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
0 ms |
384 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
240 ms |
22136 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
0 ms |
384 KB |
Output is correct |
40 |
Correct |
11 ms |
1280 KB |
Output is correct |
41 |
Correct |
255 ms |
22136 KB |
Output is correct |
42 |
Correct |
0 ms |
256 KB |
Output is correct |
43 |
Correct |
0 ms |
256 KB |
Output is correct |
44 |
Correct |
5 ms |
768 KB |
Output is correct |
45 |
Correct |
114 ms |
12120 KB |
Output is correct |
46 |
Correct |
0 ms |
256 KB |
Output is correct |
47 |
Correct |
0 ms |
256 KB |
Output is correct |
48 |
Correct |
0 ms |
384 KB |
Output is correct |
49 |
Correct |
60 ms |
5880 KB |
Output is correct |
50 |
Correct |
241 ms |
22120 KB |
Output is correct |
51 |
Correct |
243 ms |
22136 KB |
Output is correct |
52 |
Correct |
259 ms |
22264 KB |
Output is correct |
53 |
Correct |
96 ms |
12152 KB |
Output is correct |
54 |
Correct |
97 ms |
12152 KB |
Output is correct |
55 |
Correct |
240 ms |
22136 KB |
Output is correct |
56 |
Correct |
262 ms |
22136 KB |
Output is correct |
57 |
Correct |
96 ms |
12152 KB |
Output is correct |
58 |
Correct |
1 ms |
256 KB |
Output is correct |
59 |
Correct |
0 ms |
256 KB |
Output is correct |
60 |
Correct |
1 ms |
384 KB |
Output is correct |
61 |
Correct |
61 ms |
5880 KB |
Output is correct |
62 |
Correct |
245 ms |
22136 KB |
Output is correct |
63 |
Correct |
236 ms |
22136 KB |
Output is correct |
64 |
Correct |
261 ms |
22136 KB |
Output is correct |
65 |
Correct |
1 ms |
384 KB |
Output is correct |
66 |
Correct |
60 ms |
5880 KB |
Output is correct |
67 |
Correct |
246 ms |
22104 KB |
Output is correct |
68 |
Correct |
245 ms |
22304 KB |
Output is correct |
69 |
Correct |
258 ms |
22120 KB |
Output is correct |
70 |
Correct |
0 ms |
384 KB |
Output is correct |
71 |
Correct |
1 ms |
256 KB |
Output is correct |
72 |
Correct |
0 ms |
256 KB |
Output is correct |
73 |
Incorrect |
60 ms |
5880 KB |
Too many ways to get from 0 to 338, should be 1 found no less than 2 |
74 |
Halted |
0 ms |
0 KB |
- |