Submission #591567

#	Time	Username	Problem	Language	Result	Execution time	Memory
591567		APROHACK	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	215 ms	23116 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long
#define ff first
#define ss second
using namespace std;
 
int construct(vector< vector<int> > p) {
	int n = p.size();
	vector<vector<int> > answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	ll cuenta = 0, numeroDeLineas = 0, cuenta2 = 0;
	int unos[n], vis[n], LineaALaQuePertenece[n], dos[n];
	memset(vis, 0, sizeof vis);
	for(int i = 0 ; i <n ; i ++){
		cuenta=0, cuenta2=0;
		for(int j = 0 ; j < n ; j++){
			if(i!=j && p[i][j]==1)cuenta++;
			if(i!=j && p[i][j]==2)cuenta2++;
		}
		unos[i]=cuenta, dos[i]=cuenta2;
		
	}
	/// 1. uno los que solo tienen un camino
	vector<int>recorridos;
	recorridos.resize(n);
	int indxRecorrido = 0, indxCiclo=0;
	for(int cur = 0 ; cur < n ; cur++){
		if(vis[cur])continue;
		indxRecorrido = 1;
		indxCiclo=0;
		recorridos[0]=cur, vis[cur]=1;
		
		//cout << " analizando " << cur << " "<<endl;
		for(int j = 0 ; j < n ; j ++){
			if(cur!=j && p[cur][j]==1){
				recorridos[indxRecorrido]=j;
				indxRecorrido++;
				vis[j]=1;
				////cout<<j<<" ";
			}
		}

		// 2. buscar si estan conectados a algun ciclo.
		vector<int>ciclo;
		ciclo.resize(n);
		for(int j = 0 ; j < n ; j ++){
			if(p[cur][j]==2){
				ciclo[indxCiclo]=j;
				indxCiclo++;
			}
		}

		//3. tengo que unir los de recorridos por una linea
		for(int i = 1 ; i < indxRecorrido ; i++){

			//agregar linea
			LineaALaQuePertenece[recorridos[i]]=numeroDeLineas;
			
			recorridos[i-1], recorridos[i];
			answer[recorridos[i-1]][recorridos[i]]=1;
			answer[recorridos[i]][recorridos[i-1]]=1;

			//cout<<recorridos[i-1]<<" "<<recorridos[i]<<endl;

		}

		//verificar que todos tengan union de 1
		for(int i = 0 ; i < indxRecorrido ; i ++){
			int currrecorrido = 0;
			for(int j = 0 ; j < n ; j++){
				if(currrecorrido < indxRecorrido && j==recorridos[currrecorrido]){
					if(p[recorridos[i]][j]!=1)return 0;
					unos[recorridos[i]]--, unos[j]--;
					currrecorrido++;
				}else{
					if(recorridos[i]==j)continue;
					if(p[recorridos[i]][j]==1)return 0;
				}
				
			}
		}

		//cout<<"Uniones de la linea correctos\n";

		//verificar que todos esten unidos al ciclo con 2
		for(int i = 1 ; i < indxRecorrido ; i++){
			int currciclo = 0;
			for(int j = 0 ; j < n ; j++){
				if(currciclo<indxCiclo && j==ciclo[currciclo] ){
					if(p[recorridos[i]][j]!=2)return 0;
					currciclo++;
				}else if(p[recorridos[i]][j]==2)return 0;
			}
		}

		//cout<<"Uniones al ciclo correctos"<<endl;

		//agregarlinea
		LineaALaQuePertenece[cur]=numeroDeLineas;
		numeroDeLineas++;

	}

	//aqui, todas las lineas ya estan unidas, ahora hay que poner el ciclo

	for(int i = 0 ; i < n ; i ++)//cout<<LineaALaQuePertenece[i]<<" ";
	//cout<<endl;
	memset(vis, 0, sizeof vis);
	bool lineaVisitada[n];
	memset(lineaVisitada, false, sizeof lineaVisitada);
	for(int cur = 0 ; cur < n ; cur ++){
		if(dos[cur]<=0 || vis[cur] || lineaVisitada[LineaALaQuePertenece[cur]])continue;
		//cout<<"!"<<cur<<endl;
		lineaVisitada[LineaALaQuePertenece[cur]]=true;
		//set<int>lineasPorUnir;
		vector<int>representante;
		representante.push_back(cur);
		for(int j = 0 ; j < n ; j++){
			if(p[cur][j] == 2){
				vis[j]=true;
				if(!lineaVisitada[LineaALaQuePertenece[j]]){
					lineaVisitada[LineaALaQuePertenece[j]]=true;
					//cout<<"add"<<j<<endl;
					representante.push_back(j);
				}
			}
		}

		//en lineas por unir estan todas las lineas que estan pegadas al ciclo

		////to do: si el tamaño es 2 no se puede
		if(representante.size()==2){
			return 0;
		}
		for(int i = 0 ; i < representante.size() ; i++){
			ll currepresentante = 0;
			for(int j = 0 ; j < representante.size() ; j++){
				if(i==j)continue;
				if(p[representante[i]][representante[j]]!=2)return 0;
			}
		}
		for(int i = 1 ; i < representante.size() ; i++){
			//cout<<representante[i-1]<<" "<<representante[i]<<endl;
			answer[representante[i-1]][representante[i]]=1;
			answer[representante[i]][representante[i-1]]=1;
		}
		answer[representante[representante.size()-1]][representante[0]]=1;
		answer[representante[0]][representante[representante.size()-1]]=1;

		//cout<<representante[0]<< " " << representante[representante.size()-1]<<endl;
	}

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:141:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int i = 0 ; i < representante.size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    for(int j = 0 ; j < representante.size() ; j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:142:7: warning: unused variable 'currepresentante' [-Wunused-variable]
  142 |    ll currepresentante = 0;
      |       ^~~~~~~~~~~~~~~~
supertrees.cpp:148:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for(int i = 1 ; i < representante.size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~

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