Submission #305410

#TimeUsernameProblemLanguageResultExecution timeMemory
305410diegoangulo5Connecting Supertrees (IOI20_supertrees)C++14
11 / 100
293 ms22396 KiB
#include "supertrees.h" #include <vector> #include <set> using namespace std; vector< vector<int> > answer; vector< set<int> >nodos1, nodos2; vector<int> padre1, padre2, row; int n; void init(){ nodos1.resize(n); nodos2.resize(n); padre1.resize(n); padre2.resize(n); row.resize(n); for(int a=0;a<n;a++){ nodos1[a].insert(a); nodos2[a].insert(a); padre1[a] = a; padre2[a] = a; answer.push_back(row); } } set<int> juntar(set<int> a, set<int> b){ set<int> :: iterator it = b.begin(); for(;it != b.end();it++){ a.insert(*it); } return a; } int buscar2(int a){ if(padre2[a] == a)return a; return padre2[a] = buscar2(padre2[a]); } void unir2(int a, int b){ int A = buscar2(a); int B = buscar2(b); if(A != B){ padre2[max(A,B)] = min(A,B); nodos2[min(A,B)] = juntar(nodos2[A], nodos2[B]); nodos2[max(A,B)].clear(); } } int buscar1(int a){ if(padre1[a] == a)return a; return padre1[a] = buscar1(padre1[a]); } void unir1(int a, int b){ int A = buscar1(a); int B = buscar1(b); if(A != B){ padre1[max(A,B)] = min(A,B); nodos1[min(A,B)] = juntar(nodos1[A], nodos1[B]); nodos1[max(A,B)].clear(); } } void crear2(){ for(int a=0;a<n;a++){ if(nodos2[a].size() > 1){ set<int>::iterator it = nodos2[a].begin(); int anterior = *it; it++; for(;it != nodos2[a].end();it++){ answer[anterior][*it] = 1; answer[*it][anterior] = 1; anterior = *it; } it--; answer[*it][*nodos2[a].begin()] = 1; answer[*nodos2[a].begin()][*it] = 1; } } } void crear1(){ for(int a=0;a<n;a++){ if(nodos1[a].size() > 1){ set<int>::iterator it = nodos1[a].begin(); int anterior = *it; it++; for(;it != nodos1[a].end();it++){ answer[anterior][*it] = 1; answer[*it][anterior] = 1; //anterior = *it; } } } } int construct(vector<vector<int> > p) { n = p.size(); init(); for(int a=0;a<n;a++){ for(int b=0;b<n;b++){ if(a == b)continue; int val = p[a][b]; if(val == 1){ unir1(a, b); } if(val == 2){ unir2(a, b); } } } crear2(); crear1(); build(answer); return 1; }
#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...