Submission #304711

#	Time	Username	Problem	Language	Result	Execution time	Memory
304711		ocarima	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	295 ms	30096 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

#define debugsl(y) cout << #y << " = " << y << ", "
#define debug(x) debugsl(x) << endl


#define MAX_N 1001

vector<vector<int> > respuesta, entrada;
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], grupoCiclo[MAX_N], cicloGrupos[MAX_N][MAX_N]; // SUBGRAFO AL QUE PERTENECE CADA NODO

void puente(int a, int b){
    if (a == b) return;
    respuesta[a][b] = 1;
    respuesta[b][a] = 1;
}

bool checaGrupos(int a, int b){
    bool ok = true;
    if (cicloGrupos[a][b] == 1 || a == b) return true;

    for(auto i : linea[a]){
        for(auto j : linea[b]){
            if (entrada[i][j] != 2) {
                ok = false;
                break;
            }
        }
        if (!ok) break;
    }

    if (ok){
        cicloGrupos[a][b] = 1;
        cicloGrupos[b][a] = 1;
    }

    return ok;
}

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

    rep(i, 0, n - 1) grupo[i] = grupoCiclo[i] = i;

    rep(i, 0, n - 1){
        rep(j, i + 1, n - 1){
            if (p[i][j] == 0 && grupo[i] == grupo[j]) return 0;
            else if(p[i][j] == 1 && grupo[i] == i && grupo[j] == j){
                linea[i].push_back(j);
                grupo[j] = i;
            }
            else if (p[i][j] == 1 && grupo[i] != grupo[j]) return 0;
        }
        linea[i].push_back(i);
    }

    rep(i, 0, n - 1){
        rep(j, i + 1, n - 1){
            if (p[i][j] == 2 && grupo[i] == grupo[j]) return 0; // LOS NODOS PERTENECEN A LA MISMA LINEA, NO PUEDEN TENER DOS CAMINOS
            else if (p[i][j] == 0 && grupoCiclo[grupo[i]] == grupoCiclo[grupo[j]]) return 0; // ESTAN DESCONECTADOS PERO LLEGAN AL MISMO CICLO
            else if (p[i][j] == 2){
                if (!checaGrupos(grupo[i], grupo[j])) return 0; // LAS PAREJAS DE NODOS DE DOS LINEAS DISTINTAS NO TIENEN DOS CAMINOS ENTRE ELLAS
                else if (grupoCiclo[grupo[i]] == i && grupoCiclo[grupo[j]] == j){
                    ciclo[i].push_back(j);
                    grupoCiclo[grupo[j]] = grupo[i];
                }
            }
        }
    }

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

    rep(i, 0, n - 1){
	    if (ciclo[i].size() == 1) return 0; // NO PUEDE HABER UN CICLO DE SOLO 2 NODOS
	    if (ciclo[i].size() > 0){
            rep(j, 0, ciclo[i].size() - 1){
                if (j > 0) puente(ciclo[i][j], ciclo[i][j - 1]);
                if (j < ciclo[i].size() - 1) puente(ciclo[i][j], ciclo[i][j + 1]);
            }
            puente(i, ciclo[i][0]);
            puente(i, ciclo[i][ciclo[i].size() - 1]);
	    }
	}

	build(respuesta);
	return 1;
}

Compilation message (stderr)

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

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