# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1041357 | vjudge1 | Connecting Supertrees (IOI20_supertrees) | C++17 | 124 ms | 24152 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"
using namespace std;
#define AE(a,b) ans[a][b]=ans[b][a]=1
struct dsu {
int par[1010];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
void merge(int a,int b){
a=abp(a+1);
b=abp(b+1);
if(a-b)par[a]=b;
}
int CC(int n){
return abp(n+1)-1;
}
} comps, chains, CCs;
int construct(vector<vector<int>> p) {
for(auto i:p)
for(auto j:i)
if(j==3)
return 0;
int n=p.size();
vector<vector<int>>ans(n,vector<int>(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j])
CCs.merge(i,j);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i][j]==1)
chains.merge(i,j);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) if(p[i][j]==2)
comps.merge(chains.CC(i),chains.CC(j));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!p[i][j]) {
if(CCs.CC(i)==CCs.CC(j))
return 0;
} else if(p[i][j]==2)
if(chains.CC(i)==chains.CC(j))
return 0;
vector<int>thgs[1010];
for(int i=0;i<n;i++)
if(chains.CC(i)-i)
AE(chains.CC(i),i);
else thgs[comps.CC(i)].push_back(i);
for(int i=0;i<n;i++){
if(thgs[i].size()<2)continue;
if(thgs[i].size()==2)return 0;
thgs[i].push_back(thgs[i][0]);
for(int j=1;j<thgs[i].size();j++)
AE(thgs[i][j],thgs[i][j-1]);
}
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... |