제출 #573604

#제출 시각아이디문제언어결과실행 시간메모리
573604rc_catunta슈퍼트리 잇기 (IOI20_supertrees)C++14
0 / 100
0 ms212 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> padre,rnk,tam; void init(int n){ padre.assign(n,0); rnk.assign(n,1); tam.assign(n,1); for(int i=0;i<n;i++){ padre[i]=i; // Es su propio padre } } int buscar(int x){ if(padre[x]==x) return x; else return padre[x]=buscar(padre[x]); } bool mismo_conjunto(int a,int b){ return buscar(a)==buscar(b); } void unir(int a,int b){ if(!mismo_conjunto(a,b)){ a = buscar(a); b = buscar(b); if(rnk[a]>=rnk[b]){ // B se una a A padre[b] = a; tam[a]+=tam[b]; if(rnk[a]==rnk[b]) rnk[a]++; } else{ // A se une a B padre[a] = b; tam[b] += tam[a]; } } } int construct(vector<vector<int> > p) { int n = p.size(); // Armamos el Union Find vector<vector<int> > answer(n,vector<int>(n)); // Creamos la matriz de adyacencia init(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==1){ if(!mismo_conjunto(i,j)){ unir(i,j); answer[i][j]=1; answer[j][i]=1; } } } } // Ponemos a todos los representantes de los grafos linea en mapas de codificacion y decodificacion unordered_map <int,int> code,decode; int ind = 0; for(int i=0;i<padre.size();i++){ int pi = buscar(i); if(pi==i){ code[i]=ind; decode[ind]=i; ind++; } } int c_rep = code.size(); cout<<"Hay "<<c_rep<<" representantes\n"; init(c_rep); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==2){ if(code.find(i)!=code.end() and code.find(j)!=code.end()){ unir(code[i],code[j]); } } } } // Creamos los "conjuntos" unordered_map<int,vector<int> >conjuntos; for(int i=0;i<c_rep;i++){ int rep = buscar(i); //if(tam[rep]==2) return 0; // No puede haber un ciclo de 2 elementos if(conjuntos.find(rep) == conjuntos.end()){ // No existe aun esa llave conjuntos[rep] = vector<int>(); } conjuntos[rep].push_back(i); } // Construimos la matriz de adyacencia for(auto elem: conjuntos){ vector<int> lista = elem.second; if(lista.size() == 1) continue; for(int i=0;i<lista.size();i++){ int a = lista[i]; int b = lista[(i+1)%lista.size()]; answer[decode[a]][decode[b]] = 1; answer[decode[b]][decode[a]] = 1; } } build(answer); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<padre.size();i++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int i=0;i<lista.size();i++){
      |                     ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...