#include "bits/stdc++.h"
using namespace std;
#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const long long MOD = 1e9+7;
const long long INF = 1e18;
int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};
void build(vector<vector<int>> b);
struct dsu
{
vector<int> len;
vector<int> link;
void init(int n)
{
len.assign(n, 1);
link.assign(n, 0);
for(int i = 0; i<n; i++)
{
link[i] = i;
}
}
int search(int x)
{
if(x!=link[x])
link[x] = search(link[x]);
return link[x];
}
bool check(int a, int b)
{
return search(a)==search(b);
}
void join(int a, int b)
{
a = search(a);
b = search(b);
if(a!=b)
{
if(len[a]<len[b])
swap(a, b);
len[a]+=len[b];
link[b] = a;
}
}
};
int construct(vector<vector<int>> p)
{
int n = int(p[0].size());
vector<vector<int>> b(n, vector<int>(n, 0));
dsu d;
d.init(n);
bool flag = false;
for(int i = 0; i<n; i++)
{
for(int j = i+1; j<n; j++)
{
if(p[i][j]==1)
d.join(i, j);
if(p[i][j]==2)
{
d.join(i, j);
flag = true;
}
}
}
vector<vector<int>> groups(n);
for(int i = 0; i<n; i++)
{
int parent = d.search(i);
groups[parent].pb(i);
}
/*for(int i = 0; i<n; i++)
{
cout << i << ": ";
for(auto elt: groups[i])
cout << elt << ' ';
cout << endl;
}*/
if(!flag)
{
for(int i = 0; i<n; i++)
{
if(groups[i].empty())
continue;
int len = int(groups[i].size());
for(int j = 0; j<len-1; j++)
{
int A = groups[i][j];
int B = groups[i][j+1];
b[A][B] = 1;
b[B][A] = 1;
}
}
}
else
{
for(int i = 0; i<n; i++)
{
if(groups[i].empty())
continue;
if(int(groups[i].size())==2)
return 0;
int len = int(groups[i].size());
vector<int> one, two;
vector<bool> visited(n, false);
for(int j = 0; j<len; j++)
{
for(int k = j+1; k<len; k++)
{
int A = groups[i][j];
int B = groups[i][k];
if(p[A][B]==1)
{
if(!visited[A])
{
one.pb(A);
visited[A] = true;
}
if(!visited[B])
{
one.pb(B);
visited[B] = true;
}
}
if(p[A][B]==2)
{
if(!visited[A])
{
two.pb(A);
visited[A] = true;
}
if(!visited[B])
{
two.pb(B);
visited[B] = true;
}
}
}
}
if(int(two.size())<=2)
return 0;
for(int j = 0; j<int(one.size())-1; j++)
{
int A = one[j];
int B = one[j+1];
b[A][B] = 1;
b[B][A] = 1;
}
for(int j = 0; j<int(two.size())-1; j++)
{
int A = two[j];
int B = two[j+1];
b[A][B] = 1;
b[B][A] = 1;
}
int A = two[int(two.size())-1];
int B = two[0];
b[A][B] = 1;
b[B][A] = 1;
}
}
for(int i = 0; i<n; i++)
{
for(int j = i+1; j<n; j++)
{
if(p[i][j]==0&&d.check(i, j))
return 0;
if(!d.check(i, j)&&p[i][j]!=0)
return 0;
}
}
for(int i = 0; i<n; i++)
{
b[i][i] = 0;
}
build(b);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
9 ms |
1100 KB |
Output is correct |
7 |
Correct |
194 ms |
22076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
9 ms |
1100 KB |
Output is correct |
7 |
Correct |
194 ms |
22076 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1176 KB |
Output is correct |
13 |
Correct |
171 ms |
22008 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
105 ms |
12128 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5756 KB |
Output is correct |
21 |
Correct |
172 ms |
22080 KB |
Output is correct |
22 |
Correct |
177 ms |
22016 KB |
Output is correct |
23 |
Correct |
194 ms |
22008 KB |
Output is correct |
24 |
Correct |
171 ms |
22020 KB |
Output is correct |
25 |
Correct |
73 ms |
12152 KB |
Output is correct |
26 |
Correct |
71 ms |
12156 KB |
Output is correct |
27 |
Correct |
257 ms |
22008 KB |
Output is correct |
28 |
Correct |
178 ms |
22136 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 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
8 ms |
1092 KB |
Output is correct |
9 |
Correct |
183 ms |
21976 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1100 KB |
Output is correct |
13 |
Correct |
175 ms |
22032 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
812 KB |
Output is correct |
17 |
Correct |
92 ms |
12324 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
292 KB |
Output is correct |
20 |
Incorrect |
0 ms |
296 KB |
Answer gives possible 0 while actual possible 1 |
21 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Correct |
44 ms |
5772 KB |
Output is correct |
5 |
Correct |
188 ms |
22008 KB |
Output is correct |
6 |
Correct |
176 ms |
22060 KB |
Output is correct |
7 |
Correct |
185 ms |
22012 KB |
Output is correct |
8 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
9 ms |
1100 KB |
Output is correct |
7 |
Correct |
194 ms |
22076 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1176 KB |
Output is correct |
13 |
Correct |
171 ms |
22008 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
105 ms |
12128 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5756 KB |
Output is correct |
21 |
Correct |
172 ms |
22080 KB |
Output is correct |
22 |
Correct |
177 ms |
22016 KB |
Output is correct |
23 |
Correct |
194 ms |
22008 KB |
Output is correct |
24 |
Correct |
171 ms |
22020 KB |
Output is correct |
25 |
Correct |
73 ms |
12152 KB |
Output is correct |
26 |
Correct |
71 ms |
12156 KB |
Output is correct |
27 |
Correct |
257 ms |
22008 KB |
Output is correct |
28 |
Correct |
178 ms |
22136 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 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
8 ms |
1092 KB |
Output is correct |
37 |
Correct |
183 ms |
21976 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
8 ms |
1100 KB |
Output is correct |
41 |
Correct |
175 ms |
22032 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
4 ms |
812 KB |
Output is correct |
45 |
Correct |
92 ms |
12324 KB |
Output is correct |
46 |
Correct |
0 ms |
204 KB |
Output is correct |
47 |
Correct |
0 ms |
292 KB |
Output is correct |
48 |
Incorrect |
0 ms |
296 KB |
Answer gives possible 0 while actual possible 1 |
49 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
9 ms |
1100 KB |
Output is correct |
7 |
Correct |
194 ms |
22076 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1176 KB |
Output is correct |
13 |
Correct |
171 ms |
22008 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
105 ms |
12128 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5756 KB |
Output is correct |
21 |
Correct |
172 ms |
22080 KB |
Output is correct |
22 |
Correct |
177 ms |
22016 KB |
Output is correct |
23 |
Correct |
194 ms |
22008 KB |
Output is correct |
24 |
Correct |
171 ms |
22020 KB |
Output is correct |
25 |
Correct |
73 ms |
12152 KB |
Output is correct |
26 |
Correct |
71 ms |
12156 KB |
Output is correct |
27 |
Correct |
257 ms |
22008 KB |
Output is correct |
28 |
Correct |
178 ms |
22136 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 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
8 ms |
1092 KB |
Output is correct |
37 |
Correct |
183 ms |
21976 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
8 ms |
1100 KB |
Output is correct |
41 |
Correct |
175 ms |
22032 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
4 ms |
812 KB |
Output is correct |
45 |
Correct |
92 ms |
12324 KB |
Output is correct |
46 |
Correct |
0 ms |
204 KB |
Output is correct |
47 |
Correct |
0 ms |
292 KB |
Output is correct |
48 |
Incorrect |
0 ms |
296 KB |
Answer gives possible 0 while actual possible 1 |
49 |
Halted |
0 ms |
0 KB |
- |