#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 |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
0 ms |
292 KB |
Output is correct |
6 |
Correct |
8 ms |
1148 KB |
Output is correct |
7 |
Correct |
171 ms |
22704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
0 ms |
292 KB |
Output is correct |
6 |
Correct |
8 ms |
1148 KB |
Output is correct |
7 |
Correct |
171 ms |
22704 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
288 KB |
Output is correct |
11 |
Correct |
1 ms |
288 KB |
Output is correct |
12 |
Correct |
9 ms |
1176 KB |
Output is correct |
13 |
Correct |
166 ms |
22744 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
288 KB |
Output is correct |
16 |
Correct |
4 ms |
796 KB |
Output is correct |
17 |
Correct |
85 ms |
12836 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
42 ms |
6172 KB |
Output is correct |
21 |
Correct |
167 ms |
22832 KB |
Output is correct |
22 |
Correct |
174 ms |
22868 KB |
Output is correct |
23 |
Correct |
183 ms |
22716 KB |
Output is correct |
24 |
Correct |
162 ms |
22776 KB |
Output is correct |
25 |
Correct |
69 ms |
12780 KB |
Output is correct |
26 |
Correct |
66 ms |
12868 KB |
Output is correct |
27 |
Correct |
202 ms |
22724 KB |
Output is correct |
28 |
Correct |
190 ms |
22432 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 |
7 ms |
1228 KB |
Output is correct |
9 |
Correct |
185 ms |
22560 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 |
1188 KB |
Output is correct |
13 |
Correct |
181 ms |
22684 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Runtime error |
1 ms |
288 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
42 ms |
5872 KB |
Output is correct |
5 |
Correct |
171 ms |
22536 KB |
Output is correct |
6 |
Correct |
166 ms |
22572 KB |
Output is correct |
7 |
Correct |
180 ms |
22468 KB |
Output is correct |
8 |
Runtime error |
1 ms |
268 KB |
Execution killed with signal 11 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
0 ms |
292 KB |
Output is correct |
6 |
Correct |
8 ms |
1148 KB |
Output is correct |
7 |
Correct |
171 ms |
22704 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
288 KB |
Output is correct |
11 |
Correct |
1 ms |
288 KB |
Output is correct |
12 |
Correct |
9 ms |
1176 KB |
Output is correct |
13 |
Correct |
166 ms |
22744 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
288 KB |
Output is correct |
16 |
Correct |
4 ms |
796 KB |
Output is correct |
17 |
Correct |
85 ms |
12836 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
42 ms |
6172 KB |
Output is correct |
21 |
Correct |
167 ms |
22832 KB |
Output is correct |
22 |
Correct |
174 ms |
22868 KB |
Output is correct |
23 |
Correct |
183 ms |
22716 KB |
Output is correct |
24 |
Correct |
162 ms |
22776 KB |
Output is correct |
25 |
Correct |
69 ms |
12780 KB |
Output is correct |
26 |
Correct |
66 ms |
12868 KB |
Output is correct |
27 |
Correct |
202 ms |
22724 KB |
Output is correct |
28 |
Correct |
190 ms |
22432 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 |
7 ms |
1228 KB |
Output is correct |
37 |
Correct |
185 ms |
22560 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 |
1188 KB |
Output is correct |
41 |
Correct |
181 ms |
22684 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Runtime error |
1 ms |
288 KB |
Execution killed with signal 11 |
44 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
0 ms |
292 KB |
Output is correct |
6 |
Correct |
8 ms |
1148 KB |
Output is correct |
7 |
Correct |
171 ms |
22704 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
288 KB |
Output is correct |
11 |
Correct |
1 ms |
288 KB |
Output is correct |
12 |
Correct |
9 ms |
1176 KB |
Output is correct |
13 |
Correct |
166 ms |
22744 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
288 KB |
Output is correct |
16 |
Correct |
4 ms |
796 KB |
Output is correct |
17 |
Correct |
85 ms |
12836 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
42 ms |
6172 KB |
Output is correct |
21 |
Correct |
167 ms |
22832 KB |
Output is correct |
22 |
Correct |
174 ms |
22868 KB |
Output is correct |
23 |
Correct |
183 ms |
22716 KB |
Output is correct |
24 |
Correct |
162 ms |
22776 KB |
Output is correct |
25 |
Correct |
69 ms |
12780 KB |
Output is correct |
26 |
Correct |
66 ms |
12868 KB |
Output is correct |
27 |
Correct |
202 ms |
22724 KB |
Output is correct |
28 |
Correct |
190 ms |
22432 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 |
7 ms |
1228 KB |
Output is correct |
37 |
Correct |
185 ms |
22560 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 |
1188 KB |
Output is correct |
41 |
Correct |
181 ms |
22684 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Runtime error |
1 ms |
288 KB |
Execution killed with signal 11 |
44 |
Halted |
0 ms |
0 KB |
- |