Submission #483490

#	Time	Username	Problem	Language	Result	Execution time	Memory
483490		rc_catunta	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	212 ms	24056 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

vector<int> rep,rnk;

void init(int N){
	rep.assign(N,0);
	for(int i=0;i<N;i++){
		rep[i]=i;
	}
	rnk.assign(N,1);
}

int buscar(int a){
	if(rep[a]==a) return a;
	return rep[a]=buscar(rep[a]);
}

bool mismo_conjunto(int a,int b){
	return buscar(a)==buscar(b);
}

void unir(int a,int b){
	int ra=buscar(a);
	int rb=buscar(b);
	if(ra != rb){
		if(rnk[ra]>rnk[rb]){
			rep[rb]=ra;
		}
		else{
			rep[ra]=rb;
		}
	}
}

int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > answer;
	answer.assign(n,vector<int>(n));
	// Creamos el Union Find
	init(n);
	// Recorremos p
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(p[i][j]==2){
				unir(i,j);
			}
		}
	}
	// Verificar si p es correcto, si existe un grafo que lo satisfaga
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(mismo_conjunto(i,j) and p[i][j]==0){
				return 0;
			}
		}
	}
	// Si p es valido
	unordered_map<int,vector<int> >conjuntos;
	for(int i=0;i<rep.size();i++){
		int ri = buscar(i);
		if(conjuntos.find(ri)!=conjuntos.end()){
			conjuntos[ri].push_back(i);
		}
		else{
			conjuntos[ri] = vector<int>();
			conjuntos[ri].push_back(i);
		}
	}
	for(auto elem: conjuntos){
		vector<int> cont = elem.second;
		if(cont.size()==1) continue;
		if(cont.size()==2) return 0;
		for(int i=0;i<cont.size();i++){
			int na = cont[i];
			int nb = cont[(i+1)%cont.size()];
			answer[na][nb]=1;
			answer[nb][na]=1;
		}
	}
	// Imprimiendo
	/* for(auto elem: conjuntos){
		int llave = elem.first;
		vector<int> cont = elem.second;
		cout<<llave<<": ";
		for(auto x: cont){
			cout<<x<<" ";
		}
		cout<<endl;
	}*/
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i=0;i<rep.size();i++){
      |              ~^~~~~~~~~~~
supertrees.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0;i<cont.size();i++){
      |               ~^~~~~~~~~~~~

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