제출 #483490

#제출 시각아이디문제언어결과실행 시간메모리
483490rc_catunta슈퍼트리 잇기 (IOI20_supertrees)C++14
19 / 100
212 ms24056 KiB
#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; }

컴파일 시 표준 에러 (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++){
      |               ~^~~~~~~~~~~~
#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...