Submission #1076082

#TimeUsernameProblemLanguageResultExecution timeMemory
1076082Hectorungo_18Connecting Supertrees (IOI20_supertrees)C++14
11 / 100
175 ms23376 KiB
#include "supertrees.h" #include <vector> #include<bits/stdc++.h> using namespace std; const int N = 1e3+7; int p[N]; int sz[N]; int pa(int u){ p[u]=(p[u] == u ? u : pa(p[u])); return p[u]; } bool sm(int u, int v){ return pa(u) == pa(v); } void un(int u, int v){ if(sm(u, v)) return; u = pa(u); v = pa(v); if(sz[v] > sz[u]) swap(u, v); sz[u]+=sz[v]; p[v]=u; } int construct(vector<vector<int>> v) { int n = v.size(); for(int i = 0; i <= n; i++){ p[i]=i; sz[i]=1; } for(int i = 0; i < n; i++){ bool ch = 0; if(pa(i)==i) ch = 1; for(int j = i+1; j < n; j++){ if(ch){ if(v[i][j] == 0){ if(pa(j) != pa(i)) continue; else return 0; } if(pa(j) != j) return 0; un(i, j); } else{ if(pa(j) != j && pa(j) != pa(i)) return 0; } } } map<int, int> m; for(int i = 0; i < n; i++){ vector<int> a(4, 0); for(int j = 0; j < n; j++){ if(i == j) continue; a[v[i][j]]++; } if(a[1] > 0) m[i]=1; else if(a[2] > 0) m[i]=2; else if(a[3] > 0) m[i]=3; else m[i]=0; } vector<vector<int>> ans(n, vector<int> (n, 0)); for(int i = 0; i < n; i++){ if(pa(i) != i) continue; vector<vector<int>> a(4); vector<int> w; for(int j = 0; j < n; j++){ if(pa(j) == i){ w.push_back(j); a[m[j]].push_back(j); } } //aquí ya lo tengo que cambiar si quiero hacer para 3 for(int j = 0; j < w.size(); j++){ for(int k = j+1; k < w.size(); k++){ int r = m[j], s = m[k]; if(max(r, s) == 2){ if(v[j][k] != 2) return 0; } else{ if(v[j][k] != 1) return 0; } } } for(int j = 1; j < (int) a[1].size(); j++){ ans[a[1][j]][a[1][j-1]] = 1; ans[a[1][j-1]][a[1][j]] = 1; } if(a[2].size() == 0) continue; for(int j = 1; j < (int) a[2].size(); j++){ ans[a[2][j]][a[2][j-1]] = 1; ans[a[2][j-1]][a[2][j]] = 1; } if(a[1].size() == 1){ ans[a[2][0]][a[2].back()] = 1; ans[a[2].back()][a[2][0]] = 1; continue; } ans[a[2][0]][a[1].back()] = 1; ans[a[1].back()][a[2][0]] = 1; ans[a[2].back()][a[1].back()] = 1; ans[a[1].back()][a[2].back()] = 1; } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j = 0; j < w.size(); j++){
      |                        ~~^~~~~~~~~~
supertrees.cpp:81:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int k = j+1; k < w.size(); k++){
      |                              ~~^~~~~~~~~~
#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...