Submission #384769

#	Time	Username	Problem	Language	Result	Execution time	Memory
384769		Micchon	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	267 ms	24300 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;
        for(int j=0;j<n;j++){
            if(p[i][j] == 1){
                if(par[j] != -1 && par[j] != i) return 0;
                par[j] = i;
                if(i != j) answer[i][j] = 1 , answer[j][i] = 1;
            }
        }
	}

	par = vi(n,-1);
	for(int i=0;i<n;i++){
        if(par[i] != -1) continue;
        vi tmp;
        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);
            }
        }
        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;
        }
	}

	build(answer);
	return 1;
}

Compilation message (stderr)

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

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