| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 952795 | 2024-03-24T20:12:00 Z | emad234 | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#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++)
{
if(v[i].size() && v1[i].size()) return 0;
vector<bool> fnd(n);
int prv = -1;
if (vis[i])
continue;
if (v1[i].size() == 2 || v1[i].size() == 1)
return 0;
v1[i].insert(i);
for (auto x : v1[i])
{
fnd[x] = 1;
for (auto y : v1[x])
{
fnd[y] = 1;
}
}
int bg = *v1[i].begin();
auto ed1 = v1[i].begin();
ed1++;
ed1++;
int ed = *ed1
for (auto x : v1[i])
{
for (int j = 0; j < n; j++)
{
if (x == j)
continue;
if ((fnd[j] && p[x][j] != 3) || (!fnd[j] && p[x][j] == 3))
return 0;
}
vis[x] = 1;
if (prv != -1)
{
b[x][prv] = 1;
b[prv][x] = 1;
}
prv = x;
}
if (v1[i].size() > 3)
{
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;
}