#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
{
vector<int> visited(n, 0);
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;
visited[A]++;
visited[B]++;
}
int A = groups[i][len-1];
int B = groups[i][0];
b[A][B] = 1;
b[B][A] = 1;
visited[A]++;
visited[B]++;
for(int i = 0; i<n; i++)
{
if(visited[i]>2)
return 0;
}
}
}
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;
}
}
build(b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
7 ms |
1100 KB |
Output is correct |
7 |
Correct |
163 ms |
22016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
7 ms |
1100 KB |
Output is correct |
7 |
Correct |
163 ms |
22016 KB |
Output is correct |
8 |
Correct |
0 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 |
7 ms |
1100 KB |
Output is correct |
13 |
Correct |
171 ms |
22012 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
716 KB |
Output is correct |
17 |
Correct |
98 ms |
12160 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5760 KB |
Output is correct |
21 |
Correct |
177 ms |
22096 KB |
Output is correct |
22 |
Correct |
168 ms |
22028 KB |
Output is correct |
23 |
Correct |
182 ms |
22000 KB |
Output is correct |
24 |
Correct |
175 ms |
22024 KB |
Output is correct |
25 |
Correct |
83 ms |
12156 KB |
Output is correct |
26 |
Correct |
74 ms |
12168 KB |
Output is correct |
27 |
Correct |
177 ms |
22012 KB |
Output is correct |
28 |
Correct |
167 ms |
22008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
5688 KB |
Output is correct |
5 |
Correct |
175 ms |
22032 KB |
Output is correct |
6 |
Correct |
166 ms |
22020 KB |
Output is correct |
7 |
Correct |
180 ms |
22012 KB |
Output is correct |
8 |
Incorrect |
0 ms |
204 KB |
b[4][4] is not 0 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
7 ms |
1100 KB |
Output is correct |
7 |
Correct |
163 ms |
22016 KB |
Output is correct |
8 |
Correct |
0 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 |
7 ms |
1100 KB |
Output is correct |
13 |
Correct |
171 ms |
22012 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
716 KB |
Output is correct |
17 |
Correct |
98 ms |
12160 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5760 KB |
Output is correct |
21 |
Correct |
177 ms |
22096 KB |
Output is correct |
22 |
Correct |
168 ms |
22028 KB |
Output is correct |
23 |
Correct |
182 ms |
22000 KB |
Output is correct |
24 |
Correct |
175 ms |
22024 KB |
Output is correct |
25 |
Correct |
83 ms |
12156 KB |
Output is correct |
26 |
Correct |
74 ms |
12168 KB |
Output is correct |
27 |
Correct |
177 ms |
22012 KB |
Output is correct |
28 |
Correct |
167 ms |
22008 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 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
7 ms |
1100 KB |
Output is correct |
7 |
Correct |
163 ms |
22016 KB |
Output is correct |
8 |
Correct |
0 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 |
7 ms |
1100 KB |
Output is correct |
13 |
Correct |
171 ms |
22012 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
716 KB |
Output is correct |
17 |
Correct |
98 ms |
12160 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
46 ms |
5760 KB |
Output is correct |
21 |
Correct |
177 ms |
22096 KB |
Output is correct |
22 |
Correct |
168 ms |
22028 KB |
Output is correct |
23 |
Correct |
182 ms |
22000 KB |
Output is correct |
24 |
Correct |
175 ms |
22024 KB |
Output is correct |
25 |
Correct |
83 ms |
12156 KB |
Output is correct |
26 |
Correct |
74 ms |
12168 KB |
Output is correct |
27 |
Correct |
177 ms |
22012 KB |
Output is correct |
28 |
Correct |
167 ms |
22008 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 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |