Submission #745993

#	Time	Username	Problem	Language	Result	Execution time	Memory
745993		JakobZorz	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	249 ms	22808 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

vector<vector<int>> answer;
int group_ids[1000];
vector<int> groups[1000];
int group_ids2[1000];
vector<int> groups2[1000];

void connect(int a, int b){
    answer[a][b]=1;
    answer[b][a]=1;
}

int construct(vector<vector<int>> p) {
    int n = p.size();
    answer=vector<vector<int>>(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        group_ids[i]=-1;
        group_ids2[i]=-1;
    }
    
    int curr_group=0;
    for(int i=0;i<n;i++){
        if(group_ids[i]!=-1)
            continue;
        group_ids[i]=curr_group;
        groups[curr_group].push_back(i);
        for(int j=i+1;j<n;j++){
            if(group_ids[j]!=-1)
                continue;
            bool valid=true;
            for(int node:groups[curr_group]){
                if(p[node][j]!=2){
                    valid=false;
                    break;
                }
            }
            
            if(valid){
                group_ids[j]=curr_group;
                groups[curr_group].push_back(j);
            }
        }
        curr_group++;
    }
    
    /*for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==2&&group_ids[i]!=group_ids[j])
                return 0;
            if(p[i][j]==0&&group_ids[i]==group_ids[j])
                return 0;
        }
    }*/
    
    for(int i=0;i<curr_group;i++){
        if(groups[i].size()==1){
            int curr=groups[i][0];
            for(int j=0;j<n;j++){
                if(j==curr)
                    continue;
                if(p[curr][j]==1&&groups[group_ids[j]].size()!=1){
                    connect(curr,j);
                    break;
                }
            }
            continue;
        }
        /*if(groups[i].size()==2)
            return 0;*/
        for(int j=0;j<groups[i].size()-1;j++){
            connect(groups[i][j],groups[i][j+1]);
        }
        connect(groups[i][0],groups[i].back());
    }
    
    int curr_group2=0;
    for(int i=0;i<n;i++){
        if(group_ids2[i]!=-1&&group_ids[i]!=-1)
            continue;
        group_ids2[i]=curr_group;
        groups2[curr_group2].push_back(i);
        for(int j=i+1;j<n;j++){
            if(p[i][j]==1){
                group_ids2[j]=curr_group2;
                groups2[curr_group2].push_back(j);
            }
        }
        curr_group2++;
    }
    
    for(int i=0;i<curr_group2;i++){
        for(int j=0;j<groups2[i].size()-1;j++){
            connect(groups2[i][j],groups2[i][j+1]);
        }
    }
    
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j=0;j<groups[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~~
supertrees.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j=0;j<groups2[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~~~

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