Submission #745859

#	Time	Username	Problem	Language	Result	Execution time	Memory
745859		JakobZorz	슈퍼트리 잇기 (IOI20_supertrees)	C++14	19 / 100	223 ms	24140 KiB

supertrees

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

vector<vector<int>> answer;
int group_ids[1000];
vector<int> groups[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;
    
    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(p[i][j]==2){
                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)
            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());
    }
    
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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