| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1353469 | nikulid | Comparing Plants (IOI20_plants) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <vector>
using namespace std;
#include <iostream>
bool debug=0;
#define dout if(debug)cout<<"# "
vector<int> head, tsize;
vector<vector<int>> answer;
void conn(int u, int v){
answer[u][v]=1;
answer[v][u]=1;
}
void disconn(int u, int v){
answer[u][v]=0;
answer[v][u]=0;
}
int query(int u){
// find the representative of u
if(head[u]==u)return u;
return head[u]=query(head[u]);
}
void do_union(int u, int v){ // union by size :)
if(query(u)==query(v))return;
if(tsize[query(v)] > tsize[query(u)]){
// add u to v
tsize[query(v)] += tsize[query(u)];
tsize[query(u)] = 0;
head[query(u)] = query(v);
} else{
// add v to u
tsize[query(u)] += tsize[query(v)];
tsize[query(v)] = 0;
head[query(v)] = query(u);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
// assume test case 3.
// initiate tsize and head
tsize = vector<int>(n, 1);
head = vector<int>(n);
for(int i=0; i<n; i++){
head[i]=i;
}
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
if(p[y][x]==2){
do_union(y,x);
}
}
}
dout<<"debug, size:\n";
for(int i=0; i<n; i++){
dout<<tsize[i]<<" ";
}dout<<"\n";
dout<<"debug, head:\n";
for(int i=0; i<n; i++){
dout<<head[i]<<" ";
}dout<<"\n";
dout<<"debug, query:\n";
for(int i=0; i<n; i++){
dout<<query(i)<<" ";
}dout<<"\n";
// now go over everything again, and check if 2 unioned nodes have to be seperate. In this case, we return 0.
for(int y=0; y<n; y++){
if(head[y]==y && tsize[y] == 2){
// impossible to have a ring of size 2
dout<<"ring "<<y<<" has size 2, which is impossible.\n";
return 0;
}
for(int x=0; x<n; x++){
if(p[y][x] == 0 && query(y)==query(x)){
dout<<"no solution exists, because: \n";
dout<<"p["<<y<<"]["<<x<<"] = " << p[y][x]<<" = 0, and query("<<y<<")="<<query(y)<<" == query("<<x<<")="<<query(x)<<"\n";
return 0;
}
}
}
vector<int> last(n);
for(int i=0; i<n; i++){
last[i] = i;
}
// now we know there exists a construction which meets the requirements
dout<<"there exists a valid solution.\n";
answer = vector<vector<int>>(n, vector<int>(n,0));
int chead;
vector<int> ncon(n,0);
for(int i=0; i<n; i++){
chead = query(i);
if(chead == i){
// this is the representative of a ring, or a lone node.
last[chead] = chead;
} else{
// this is a part of a ring.
if(ncon[last[chead]] < 2)disconn(last[chead], chead);
conn(last[chead], i);
conn(i, chead);
last[chead] = i;
ncon[i]=1 + (chead != last[chead]);
}
}
build(answer);
return 1;
}