#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;
int len = int(groups[i].size());
vector<int> one, two;
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)
{
one.pb(A);
one.pb(B);
}
if(p[A][B]==2)
{
two.pb(A);
two.pb(B);
}
}
}
if(int(two.size())==2)
return 0;
for(int j = 0; j<int(one.size())-1; j++)
{
int A = groups[i][j];
int B = groups[i][j+1];
b[A][B] = 1;
b[B][A] = 1;
}
for(int j = 0; j<int(two.size())-1; j++)
{
int A = groups[i][j];
int B = groups[i][j+1];
b[A][B] = 1;
b[B][A] = 1;
}
int A = groups[i][int(two.size())-1];
int B = groups[i][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 |
1 ms |
244 KB |
Output is correct |
3 |
Correct |
0 ms |
220 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1192 KB |
Output is correct |
7 |
Correct |
164 ms |
24136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
244 KB |
Output is correct |
3 |
Correct |
0 ms |
220 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1192 KB |
Output is correct |
7 |
Correct |
164 ms |
24136 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
268 KB |
Output is correct |
12 |
Correct |
10 ms |
1148 KB |
Output is correct |
13 |
Correct |
164 ms |
24044 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
84 ms |
14044 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 |
6148 KB |
Output is correct |
21 |
Correct |
219 ms |
24008 KB |
Output is correct |
22 |
Correct |
178 ms |
24028 KB |
Output is correct |
23 |
Correct |
179 ms |
24104 KB |
Output is correct |
24 |
Correct |
188 ms |
24084 KB |
Output is correct |
25 |
Correct |
69 ms |
14060 KB |
Output is correct |
26 |
Correct |
87 ms |
14048 KB |
Output is correct |
27 |
Correct |
194 ms |
23916 KB |
Output is correct |
28 |
Correct |
176 ms |
23972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
224 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
10 ms |
1220 KB |
Output is correct |
9 |
Correct |
199 ms |
23276 KB |
Output is correct |
10 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
292 KB |
Output is correct |
4 |
Correct |
45 ms |
6232 KB |
Output is correct |
5 |
Correct |
178 ms |
23392 KB |
Output is correct |
6 |
Correct |
165 ms |
23364 KB |
Output is correct |
7 |
Correct |
236 ms |
23420 KB |
Output is correct |
8 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
244 KB |
Output is correct |
3 |
Correct |
0 ms |
220 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1192 KB |
Output is correct |
7 |
Correct |
164 ms |
24136 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
268 KB |
Output is correct |
12 |
Correct |
10 ms |
1148 KB |
Output is correct |
13 |
Correct |
164 ms |
24044 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
84 ms |
14044 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 |
6148 KB |
Output is correct |
21 |
Correct |
219 ms |
24008 KB |
Output is correct |
22 |
Correct |
178 ms |
24028 KB |
Output is correct |
23 |
Correct |
179 ms |
24104 KB |
Output is correct |
24 |
Correct |
188 ms |
24084 KB |
Output is correct |
25 |
Correct |
69 ms |
14060 KB |
Output is correct |
26 |
Correct |
87 ms |
14048 KB |
Output is correct |
27 |
Correct |
194 ms |
23916 KB |
Output is correct |
28 |
Correct |
176 ms |
23972 KB |
Output is correct |
29 |
Correct |
0 ms |
292 KB |
Output is correct |
30 |
Correct |
0 ms |
292 KB |
Output is correct |
31 |
Correct |
0 ms |
224 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
10 ms |
1220 KB |
Output is correct |
37 |
Correct |
199 ms |
23276 KB |
Output is correct |
38 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
244 KB |
Output is correct |
3 |
Correct |
0 ms |
220 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1192 KB |
Output is correct |
7 |
Correct |
164 ms |
24136 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
268 KB |
Output is correct |
12 |
Correct |
10 ms |
1148 KB |
Output is correct |
13 |
Correct |
164 ms |
24044 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
6 ms |
768 KB |
Output is correct |
17 |
Correct |
84 ms |
14044 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 |
6148 KB |
Output is correct |
21 |
Correct |
219 ms |
24008 KB |
Output is correct |
22 |
Correct |
178 ms |
24028 KB |
Output is correct |
23 |
Correct |
179 ms |
24104 KB |
Output is correct |
24 |
Correct |
188 ms |
24084 KB |
Output is correct |
25 |
Correct |
69 ms |
14060 KB |
Output is correct |
26 |
Correct |
87 ms |
14048 KB |
Output is correct |
27 |
Correct |
194 ms |
23916 KB |
Output is correct |
28 |
Correct |
176 ms |
23972 KB |
Output is correct |
29 |
Correct |
0 ms |
292 KB |
Output is correct |
30 |
Correct |
0 ms |
292 KB |
Output is correct |
31 |
Correct |
0 ms |
224 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
10 ms |
1220 KB |
Output is correct |
37 |
Correct |
199 ms |
23276 KB |
Output is correct |
38 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
39 |
Halted |
0 ms |
0 KB |
- |