| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 827014 | 2023-08-16T08:00:37 Z | tomruk | Comparing Plants (IOI20_plants) | C++17 | 0 ms | 0 KB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n,(vector<int>(n,0)));
vector<bool> used(n,0);
function<void(int)> dfs = [&](int v)->void{
used[v] = 1;
for(int i = 0;i<n;i++){
if(!used[i] && p[v][i] == 1){
dfs(i);
answer[v][i] = 1;
answer[i][v] = 1;
}
}
};
for(int i = 0;i<n;i++){
if(used[i])continue;
int now = i;
vector<int> tmp;
int num = -1;
set<int> s;
for(int j = 0;j<n;j++){
if(p[now][j] >= 2){
if(num == -1)
num = p[now][j];
if(num != p[now][j])
return 0;
s.insert(j);
}
}
while(s.size()){
tmp.push_back(now);
used[now] = 1;
vector<int> del;
for(auto u:s){
if(p[now][u] < 2){
del.push_back(u);
}
}
for(auto u:del)
s.erase(u);
if(s.empty())
break;
now = *s.begin();
}
if(tmp.empty())
continue;
if(tmp.size() < 3){
return 0;
}
for(int i = 0;i<tmp.size();i++){
answer[tmp[i]][tmp[(i + 1)%tmp.size()]] = 1;
answer[tmp[(i + 1)%tmp.size()]][tmp[i]] = 1;
}
if(num == 3){
if(tmp.size() < 4)
return 0;
answer[tmp[i]][tmp[(i + 2)%tmp.size()]] = 1;
answer[tmp[(i + 2)%tmp.size()]][tmp[i]] = 1;
}
for(auto u:tmp){
dfs(u);
}
}
for(int i = 0;i<n;i++){
// cout << used[i] << endl;
if(!used[i])
dfs(i);
}
build(answer);
return 1;
}