# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1013205 | Luvidi | Connecting Supertrees (IOI20_supertrees) | C++17 | 170 ms | 24400 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 "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int par[1000],sz[1000];
vector<vector<int>> ans;
int rep(int x){
while(x!=par[x])x=par[x];
return x;
}
void join(int x,int y){
x=rep(x);y=rep(y);
if(x==y)return;
if(sz[x]>sz[y])swap(x,y);
par[x]=y;
sz[y]+=sz[x];
}
void edge(int x,int y){
ans[x][y]=1;
ans[y][x]=1;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
for(int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
}
for (int i=0;i<n;i++){
vector<int> row;
row.resize(n);
ans.push_back(row);
}
bool s2=1,s3=1;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j]){
s2&=p[i][j]==1;
s3&=p[i][j]==2;
join(i,j);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j]==0){
if(rep(i)==rep(j))return 0;
}else{
if(rep(i)!=rep(j))return 0;
}
}
}
vector<int> v[n];
for(int i=0;i<n;i++)v[rep(i)].push_back(i);
for(int i=0;i<n;i++)if(v[i].size()>1){
if(s2){
for(int j=0;j+1<v[i].size();j++){
edge(v[i][j],v[i][j+1]);
}
}else{
if(v[i].size()==2)return 0;
for(int j=0;j+1<v[i].size();j++){
edge(v[i][j],v[i][j+1]);
}
edge(v[i][0],v[i].back());
}
}
build(ans);
return 1;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |