#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
int dsu[mxN];
int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
void merge(int a, int b) { dsu[find(b)] = find(a); }
int construct(std::vector<std::vector<int>> p)
{
vector<vector<int>> b;
int n = p.size(), m = p.size();
b.resize(n);
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < n; i++)
b[i].resize(m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (p[i][j] == 1)
{
if (find(i) != find(j))
{
merge(i, j);
b[i][j] = 1;
b[j][i] = 1;
}
}
}
}
vector<vector<int>> ty;
vector<set<int>> v, v1;
v.resize(n);
v1.resize(n);
ty.resize(n);
for (int i = 0; i < n; i++)
{
ty[i].resize(n);
for (int j = 0; j < m; j++)
{
ty[i][j] = -1;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == j)
continue;
if (find(i) == find(j))
{
if (p[i][j] != 1)
return 0;
}
else
{
if (ty[find(i)][find(j)] != -1 && p[i][j] != ty[find(i)][find(j)])
return 0;
if (p[i][j] == 2)
{
v[find(i)].insert(find(j));
v[find(j)].insert(find(i));
}
if (p[i][j] == 3)
{
v1[find(i)].insert(find(j));
v1[find(j)].insert(find(i));
}
ty[find(i)][find(j)] = p[i][j];
}
}
}
vector<bool> vis(n);
for (int i = 0; i < n; i++)
{
vector<bool> fnd(n);
int prv = -1;
if (vis[i])
continue;
if (v[i].size() == 1)
return 0;
v[i].insert(i);
for (auto x : v[i])
{
fnd[x] = 1;
for (auto y : v[x])
{
fnd[y] = 1;
}
}
for (auto x : v[i])
{
for (int j = 0; j < n; j++)
{
if (x == j)
continue;
if (fnd[j] && p[x][j] != 2)
return 0;
}
vis[x] = 1;
if (prv != -1)
{
b[x][prv] = 1;
b[prv][x] = 1;
}
prv = x;
}
if (v[i].size() >= 2)
{
b[*v[i].begin()][*v[i].rbegin()] = 1;
b[*v[i].rbegin()][*v[i].begin()] = 1;
}
}
for (int i = 0; i < n; i++)
vis[i] = 0;
for (int i = 0; i < n; i++)
{
vector<bool> fnd(n);
int prv = -1;
if (vis[i])
continue;
v1[i].insert(i);
if (v1[i].size() == 2 || v1[i].size() == 3)
return 0;
for (auto x : v1[i])
{
fnd[x] = 1;
for (auto y : v1[x])
{
fnd[y] = 1;
}
}
int bg;
int ed = *v1[i].begin();
bg = ed;
ed++;
ed++;
for (auto x : v1[i])
{
for (int j = 0; j < n; j++)
{
if (x == j)
continue;
if (fnd[j] && p[x][j] != 3)
return 0;
}
vis[x] = 1;
if (prv != -1)
{
b[x][prv] = 1;
b[prv][x] = 1;
}
prv = x;
}
b[*v1[i].begin()][*v1[i].rbegin()] = 1;
b[*v1[i].rbegin()][*v1[i].begin()] = 1;
b[bg][ed] = 1;
b[ed][bg] = 1;
}
build(b);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
