Submission #384778

#	Time	Username	Problem	Language	Result	Execution time	Memory
384778		Micchon	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	274 ms	24172 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>

vi par;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(p[i][j] == 3) return 0;
	vector<vi> answer(n,vi(n,0));
	par = vi(n,-1);
	vi cyc(n,0);
	for(int i=0;i<n;i++){
        if(par[i] != -1) continue;
        cyc[i] = 1;
        vi tmp;
        for(int j=0;j<n;j++){
            if(p[i][j] == 1){
                if(par[j] != -1 && par[j] != i) return 0;
                par[j] = i;
                tmp.push_back(j);
                if(i != j) answer[i][j] = 1 , answer[j][i] = 1;
            }
        }
        for(int j=0;j<tmp.size();j++){
            for(int k=0;k<tmp.size();k++){
                if(p[tmp[j]][tmp[k]] != 1) return 0;
            }
        }
	}

	par = vi(n,-1);
	for(int i=0;i<n;i++){
        if(par[i] != -1) continue;
        vi tmp;
        vi tmp2;
        for(int j=0;j<n;j++){
            if(p[i][j] != 0){
                if(par[j] != -1 && par[j] != i) return 0;
                par[j] = i;
                if(cyc[j]) tmp.push_back(j);
                tmp2.push_back(j);
            }
        }
        if(tmp.size() == 2) return 0;
        if(tmp.size() < 2) continue;
        for(int j=0;j<tmp.size();j++){
            int i1 = tmp[j] , i2 = tmp[(j+1)%tmp.size()];
            answer[i1][i2] = 1 , answer[i2][i1] = 1;
        }
        for(int j=0;j<tmp2.size();j++){
            for(int k=0;k<tmp2.size();k++){
                if(p[tmp2[j]][tmp2[k]] == 0) return 0;
            }
        }
	}

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<tmp.size();j++){
      |                     ~^~~~~~~~~~~
supertrees.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for(int k=0;k<tmp.size();k++){
      |                         ~^~~~~~~~~~~
supertrees.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j=0;j<tmp.size();j++){
      |                     ~^~~~~~~~~~~
supertrees.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=0;j<tmp2.size();j++){
      |                     ~^~~~~~~~~~~~
supertrees.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int k=0;k<tmp2.size();k++){
      |                         ~^~~~~~~~~~~~

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