#include "bits/stdc++.h"
using namespace std;
#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);
for(int i = 0; i<n; i++)
{
for(int j = i+1; j<n; j++)
{
if(p[i][j]==1)
d.join(i, j);
}
}
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;
}*/
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;
}
}
for(auto group: groups)
{
int len = int(group.size());
for(int i = 0; i<len; i++)
{
for(int j = 0; j<len; j++)
{
if(p[i][j]==0&&d.check(i, j))
return 0;
}
}
}
build(b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 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 |
175 ms |
22016 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 |
Correct |
1 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 |
175 ms |
22016 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 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 |
177 ms |
22072 KB |
Output is correct |
14 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
204 KB |
Too few ways to get from 0 to 1, should be 2 found 0 |
3 |
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 |
1 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 |
175 ms |
22016 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 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 |
177 ms |
22072 KB |
Output is correct |
14 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
15 |
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 |
1 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 |
175 ms |
22016 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 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 |
177 ms |
22072 KB |
Output is correct |
14 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 1 while actual possible 0 |
15 |
Halted |
0 ms |
0 KB |
- |