Submission #405282

#	Time	Username	Problem	Language	Result	Execution time	Memory
405282		ngrace	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	281 ms	24188 KiB

supertrees

#include "supertrees.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	
	bool onesOnlyOnDiag=true;
	vector<int> present(4,0);
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && p[i][j]==1){
                onesOnlyOnDiag=false;
            }
            present[p[i][j]]=1;
        }
    }
    
	bool poss=true;
	
    if(present[3]){//sub 6 - no additional constraints
        poss=false;
    }
    else if(present[2]&&present[1] && !onesOnlyOnDiag){//sub 5&4 - 0's,1's and 2's, 4 there is a solution, 5 there may not be
        map<vector<int>,vector<int>> cycles;
        map<vector<int>,vector<int>> lines;
        set<vector<int>> mix;
        vector<int> in_mix;
        
        for(int i=0;i<n;i++){
            bool ones=true;
            bool twos=true;
            for(int j=0;j<n;j++){
                if(p[i][j]==1 && i!=j){
                    twos=false;
                }
                if(p[i][j]==2){
                    ones=false;
                }
            }
            if(twos){
                p[i][i]=2;
                if(cycles.find(p[i])==cycles.end()){
                    vector<int> tmp(n,0);
                    cycles[p[i]]=tmp;
                }
                cycles[p[i]][i]=2;
            }
            else if(ones){
                if(lines.find(p[i])==lines.end()){
                    vector<int> tmp(n,0);
                    lines[p[i]]=tmp;
                }
                lines[p[i]][i]=1;
            }
            else{
                in_mix.push_back(i);
                vector<int> tmp(n,0);
                for(int j=0;j<n;j++){
                    if(p[i][j]>0){
                        tmp[j]=1;
                    }
                }
                mix.insert(tmp);
            }
        }
        
        sort(in_mix.begin(),in_mix.end());
        
        for(auto&it:cycles){
            vector<int> key = it.first;
            vector<int> val = it.second;
            
            /**if(key!=val){
                poss=false;
                break;
            }**/
            
            bool m=false;
            int count=0;
            int last=-1;
            int first=-1;
            for(int i=0;i<n;i++){
                if(key[i]==2){
                    if(in_mix.size()>0){
                        auto lb=lower_bound(in_mix.begin(),in_mix.end(),i);
                        if((*lb)==i){
                            m=true;
                            break;
                        }
                    }
                    
                    count++;
                    if(last==-1){
                        last=i;
                        first=i;
                    }
                    else{
                        answer[i][last]=1;
                        answer[last][i]=1;
                        last=i;
                    }
                }
            }
            
            if(m){
                continue;
            }
            
            if(key!=val || count==2){
                poss=false;
                break;
            }
            
            if(first!=last && count>0){
                answer[first][last]=1;
                answer[last][first]=1;
            }
        }
        
        for(auto&it:lines){
            vector<int> key = it.first;
            vector<int> val = it.second;
            
            if(key!=val){
                poss=false;
                break;
            }
            
            int last=-1;
            for(int i=0;i<n;i++){
                if(key[i]){
                    if(last==-1){
                        last=i;
                    }
                    else{
                        answer[i][last]=1;
                        answer[last][i]=1;
                    }
                }
            }
        }
        
        for(auto&it:mix){
            if(!poss){
                break;
            }
            
            vector<int> in_lines(1,-1);
            vector<vector<int>> mlines(1,vector<int>(0,0));
            vector<int> cycle;
                        
            for(int i=0;i<n;i++){//put in lines or cycle
                if(it[i]){
                    if(in_lines.size()>0){
                        sort(in_lines.begin(),in_lines.end());
                        auto lb=lower_bound(in_lines.begin(),in_lines.end(),i);
                        if((*lb)==i){
                            continue;
                        }
                    }
                    
                    bool ones=false;
                    for(int j=0;j<n;j++){
                        if(i!=j){
                            if(p[i][j]==1){
                                ones=true;
                                mlines[mlines.size()-1].push_back(j);
                                in_lines.push_back(j);
                            }
                        }
                    }
                    if(ones){
                        mlines[mlines.size()-1].push_back(i);
                        in_lines.push_back(i);
                        vector<int> tmp;
                        mlines.push_back(tmp);
                    }
                    else{
                        cycle.push_back(i);
                    }
                }
            }
            
            if(mlines.size()>0){
                mlines.pop_back();
            }
            
            for(vector<int>&pt:mlines){
                if(pt.size()>0){
                    cycle.push_back(pt[0]);
                }
            }
            
            if(cycle.size()>2){
                answer[cycle[0]][cycle[cycle.size()-1]]=1;
                answer[cycle[cycle.size()-1]][cycle[0]]=1;
                for(int i=0;i<cycle.size()-1;i++){
                    answer[cycle[i]][cycle[i+1]]=1;
                    answer[cycle[i+1]][cycle[i]]=1;
                }
            }
            else{
                poss=false;
            }
            
            
            for(vector<int>& pt:mlines){
                for(int i=1;i<pt.size();i++){
                    for(int j=1;j<pt.size();j++){
                        if(p[pt[i]][pt[j]]!=1){
                            poss=false;
                        }
                    }
                    answer[pt[i]][pt[0]]=1;
                    answer[pt[0]][pt[i]]=1;
                }
            }
        }
    }
    else if(present[2]){//sub 3 - 2's and 0's
        map<vector<int>,vector<int>> cycles;
        
        for(int i=0;i<n;i++){
            p[i][i]=2;
            if(cycles.find(p[i])==cycles.end()){
                vector<int> tmp(n,0);
                cycles[p[i]]=tmp;
            }
            cycles[p[i]][i]=2;
        }
        
        for(auto&it:cycles){
            vector<int> key = it.first;
            vector<int> val = it.second;
            
            if(key!=val){
                poss=false;
                break;
            }
            
            
            int count=0;
            int last=-1;
            int first=-1;
            for(int i=0;i<n;i++){
                if(key[i]==2){
                    count++;
                    if(last==-1){
                        last=i;
                        first=i;
                    }
                    else{
                        answer[i][last]=1;
                        answer[last][i]=1;
                        last=i;
                    }
                }
            }
            
            if(key!=val || count==2){
                poss=false;
                break;
            }
            
            if(first!=last){
                answer[first][last]=1;
                answer[last][first]=1;
            }
        }
    }
    else if(present[1] && present[0]){//sub 2 - 1's and 0's
        map<vector<int>,vector<int>> lines;
        
        for(int i=0;i<n;i++){
            if(lines.find(p[i])==lines.end()){
                vector<int> tmp(n,0);
                lines[p[i]]=tmp;
            }
            lines[p[i]][i]=1;
        }
        
        for(auto&it:lines){
            vector<int> key = it.first;
            vector<int> val = it.second;
            
            if(key!=val){
                poss=false;
                break;
            }
            
            int last=-1;
            for(int i=0;i<n;i++){
                if(key[i]){
                    if(last==-1){
                        last=i;
                    }
                    else{
                        answer[i][last]=1;
                        answer[last][i]=1;
                    }
                }
            }
        }
    }
    else{//sub 1 - just 1's
        for(int i=0;i<n-1;i++){
            answer[i][i+1]=1;
            answer[i+1][i]=1;
        }
    }
    
    
    if(poss){
        build(answer);
        return 1;
    }
    else{
        return 0;
    }
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:207:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |                 for(int i=0;i<cycle.size()-1;i++){
      |                             ~^~~~~~~~~~~~~~~
supertrees.cpp:218:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |                 for(int i=1;i<pt.size();i++){
      |                             ~^~~~~~~~~~
supertrees.cpp:219:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |                     for(int j=1;j<pt.size();j++){
      |                                 ~^~~~~~~~~~

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