Submission #304610

#	Time	Username	Problem	Language	Result	Execution time	Memory
304610		ocarima	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	251 ms	22264 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
int grupo[MAX_N]; // SUBGRAFO AL QUE PERTENECE CADA NODO

int construct(std::vector<std::vector<int> > p) {
	int n = p.size();

    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
                linea[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
        }
    }

	vector<vector<int> > respuesta;
	rep(i, 0, n - 1){
	    vector<int> fila;
	    fila.resize(n);
	    respuesta.push_back(fila);
	}

	rep(i, 0, n - 1){
	    for(auto nodo : linea[i]){
            respuesta[nodo][i] = 1;
            respuesta[i][nodo] = 1;
	    }
	}

	build(respuesta);
	return 1;
}

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