Submission #1241588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241588		moondarkside	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	328 ms	26156 KiB

supertrees

#include<bits/stdc++.h>
using namespace std;

void build(vector<vector<int>> b);


vector<vector<int>> Req;
vector<int> UF;
vector<vector<int>> Build;

int getTop(int a){
    auto b=UF;
    auto x=a;
    if(UF[a]==a){
        return a;
    }
    UF[a]=getTop(UF[a]);
    return UF[a];
}

void join(int a,int b){
    UF[getTop(b)]=getTop(a);
}

void connect(int i,int j){
    Build[i][j]=1;
    Build[j][i]=1;
}

int buildOneTree(vector<int> Tree){
    for(int i=0;i<Tree.size();i++){
        for(int j=i+1;j<Tree.size();j++){
            if(Req[Tree[i]][Tree[j]]>1){
                return 0;
            }
        }
    }
        
    for(int i=1;i<Tree.size();i++){
        connect(Tree[i],Tree[0]);
    }
    return 1;
}

int BuildTree(vector<int> Tree){
    
    int n=Tree.size();
    
    UF=vector<int>(n);
    
    for(int i=0;i<n;i++){
        UF[i]=i;
    }
    
    int delta=0;
    
    for(int i=0;i<n;i++){
        
        for(int j=i+1;j<n;j++){
            
            if(Req[Tree[i]][Tree[j]]==0){
                return 0;
            }
            
            if(Req[Tree[i]][Tree[j]]==1){
                join(i,j);
            }
            
            if(Req[Tree[i]][Tree[j]]>1 && delta==0){
                delta=Req[Tree[i]][Tree[j]];
            }
            
            if(Req[Tree[i]][Tree[j]]>1 && Req[Tree[i]][Tree[j]]!=delta){
                return 0;
            }
            
            
        }
        
    }
    
    
    vector<vector<int>> SubTrees;
    
    for(int i=0;i<n;i++){
        if(UF[i]!=-1){
            vector<int> NewTree;
            int eq=UF[i];
            for(int j=i;j<n;j++){
                if(UF[j]==eq){
                    
                    NewTree.push_back(Tree[j]);
                    UF[j]=-1;
                    
                }
                
            }
            SubTrees.push_back(NewTree);
            
        }
    }
    
    if(delta<3){
      if(SubTrees.size()==2){
        return 0;
    }
    
    if(SubTrees.size()==1){
        return buildOneTree(SubTrees[0]);
    }
    
    for(int i=0;i<SubTrees.size();i++){
        if(buildOneTree(SubTrees[i])==0){
            return 0;
        }
        
        connect(SubTrees[i][0],SubTrees[(i+1)%SubTrees.size()][0]);
    }  
    return 1;
    }
    
    
    if(SubTrees.size()!=4){
        return 0;
    }
    connect(SubTrees[0][0],SubTrees[SubTrees.size()-1][0]);
    connect(SubTrees[1][0],SubTrees[SubTrees.size()-1][0]);
    
    
    if(buildOneTree(SubTrees[SubTrees.size()-1])==0){
            return 0;
    }
    
    for(int i=0;i<SubTrees.size()-1;i++){
        if(buildOneTree(SubTrees[i])==0){
            return 0;
        }
        
        connect(SubTrees[i][0],SubTrees[(i+1)%(SubTrees.size()-1)][0]);
    }  
    return 1;
    
};


int construct(vector<vector<int>> p){
    Req=p;
    
    int n=p.size();
    Build=vector<vector<int>>(n,vector<int>(n));
    UF=vector<int>(n);
    for(int i=0;i<n;i++){
        UF[i]=i;
    }
    
    for(int i=0;i<n;i++){
       for(int j=i+1;j<n;j++){
            if(p[i][j]>0){
                join(i,j);
            }
        } 
    }
    
    vector<vector<int>> SubTrees;
    
    for(int i=0;i<n;i++){
        if(UF[i]!=-1){
            vector<int> Tree;
            int eq=UF[i];
            for(int j=i;j<n;j++){
                if(UF[j]==eq){
                    
                    Tree.push_back(j);
                    UF[j]=-1;
                    
                }
                
            }
            SubTrees.push_back(Tree);
            
        }
    }
    
    for(int i=0;i<SubTrees.size();i++){
        if(BuildTree(SubTrees[i])==0){
            return 0;
        }
    }
    
    build(Build);
    
    return 1;
    
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4