Submission #304623

#	Time	Username	Problem	Language	Result	Execution time	Memory
304623		ocarima	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

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

using namespace std;

#define rep(i, a, b) for(int i = (a); i <= (b); i++)

#define MAX_N 1001

vector<int> linea[MAX_N]; // VECTOR PARA GUARDAR LOS NODOS DE CADA LINEA
vector<int> ciclo[MAX_N]; // NODOS EN CADA CICLO
int grupo[MAX_N]; // SUBGRAFO AL QUE PERTENECE CADA NODO

int construct(std::vector<std::vector<int> > p) {
	int n = p.size();
	vector<vector<int> > respuesta;
	rep(i, 0, n - 1){
	    vector<int> fila;
	    fila.resize(n);
	    respuesta.push_back(fila);
	}

    rep(i, 0, n - 1) grupo[i] = i; // INICIALMENTE CADA NODO ESTÁ EN SU PROPIO GRUPO
    rep(i, 0, n - 1){
        rep(j, i + 1, n - 1){
            if (p[i][j] == 0 && grupo[i] == grupo[j]) return 0; // LOS NODOS ESTAN DESCONECTADOS ENTRE ELLOS PERO PERTENECEN AL MISMO GRUPO
            else if(p[i][j] == 1 && grupo[i] == i && grupo[j] == j){ // EL PRIMER QUE ENCUENTRAS DEL GRUPO LOS AGREGA TODOS A SU GRUPO
                ciclo[i].push_back(j);
                grupo[j] = i;
            }
            else if (p[i][j] == 1 && grupo[i] != grupo[j]) return 0; // SI ESTAN CONECTADOS Y NO ESTAN EN EL MISMO GRUPO EL SUBGRAFO ES INVALIDO
        }
    }

	rep(i, 0, n - 1){
	    if (ciclo[i].size() > 0){
            rep(j, 1, ciclo[i].size() - 1){
                respuesta[ciclo[i][j]][ciclo[i][j - 1]] = 1;
                respuesta[ciclo[i][j - 1]][ciclo[i][j]] = 1;
            }
            respuesta[ciclo[i][0]][ciclo[i][ciclo[i].size() - 1]] = 1;
            respuesta[ciclo[i][ciclo[i].size() - 1]][ciclo[i][0]] = 1;
	    }
	}

	build(respuesta);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, a, b) for(int i = (a); i <= (b); i++)
      |                                         ^
supertrees.cpp:37:13: note: in expansion of macro 'rep'
   37 |             rep(j, 1, ciclo[i].size() - 1){
      |             ^~~

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