| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 666993 | atigun | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include"supertrees.h"
using namespace std;
typedef long long ll;
struct dsu{
vector<int> parent, size;
int N;
void assign(int dsusize){
N = dsusize;
parent.assign(N, 0);
iota(parent.begin(), parent.end(), 0);
size.assign(N, 1);
}
int find(int v){
return parent[v] = (parent[v] == v ? v : find(parent[v]));
}
void merge(int v, int u){
if(find(v) == find(u))
return;
if(size[find(v)] < size[find(u)])
swap(u, v);
size[find(v)]+= size[find(u)];
parent[find(u)] = parent[find(v)];
}
bool is_same(int v, int u){
return (find(v) == find(u));
}
};
int n;
vector<vector<int>> p;
dsu DSU;
vector<vector<int>> ans;
void make_edge(int x, int y){
ans[x][y] = ans[y][x] = 1;
}
int construct(vector<vector<int>>& p){
n = p.size();
ans.assign(n, vector<int>(n));
DSU.assign(n);
bool ok = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
ok&= (p[i][j] == p[j][i]);
if(p[i][j])
DSU.merge(i, j);
}
ok&= (p[i][i] == 1);
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ok&= (DSU.is_same(i, j) == (p[i][j] != 0));
if(!ok)
return 0;
vector<vector<int>> groups(n);
for(int i = 0; i < n; i++)
groups[DSU.find(i)].push_back(i);
for(vector<int> &G : groups){
if(G.empty())
continue;
vector<int> all_two, is_two(n, 1);
all_two.reserve(n);
for(int I : G){
for(int j = 0; j < n; j++){
is_two[I]&= (I == j || p[I][j] == 2 || p[I][j] == 0);
}
if(is_two[I])
all_two.push_back(I);
}
for(int i = 1; i < all_two.size(); i++)
make_edge(all_two[i-1], all_two[i]);
vector<int> color(n, -1);
color[0] = 0;
for(int i = 0; i < G.size(); i++){
if(is_two[G[i]])
continue;
for(int j = i+1; j < G.size(); j++){
if(is_two[G[j]])
continue;
if(p[G[i]][G[j]] == 1){
ok&= (color[G[j]] == -1 || color[G[j]] == color[G[i]]);
color[j] = color[i];
} else if(p[G[i]][G[j]] == 2){
ok&= (color[G[j]] == -1 || color[G[j]] == color[G[i]]^1);
color[G[j]] = color[G[i]]^1;
}
}
}
if(!ok)
break;
vector<vector<int>> side(2);
for(int I : G){
if(is_two[I])
continue;
side[color[I]].push_back(I);
}
for(int i = 1; i < side[0].size(); i++)
make_edge(side[0][i-1], side[0][i]);
for(int i = 1; i < side[1].size(); i++)
make_edge(side[1][i-1], side[1][i]);
if(all_two.size()){
if(side[0].size() && side[1].size()){
make_edge(side[0].back(), side[1][0]);
make_edge(side[0].back(), all_two[0]);
make_edge(side[1][0], all_two.back());
} else if(side[0].size() && side[1].empty()){
make_edge(side[0].back(), all_two[0]);
make_edge(side[0].back(), all_two.back());
} else if(side[0].empty() && side[1].size()){
make_edge(side[0][0], all_two.back());
make_edge(side[0][0], all_two[0]);
}
} else{
ok&= (side[1].empty());
}
}
if(!ok)
return 0;
build(ans);
return 1;
}