Submission #779199

#TimeUsernameProblemLanguageResultExecution timeMemory
779199kamelfanger83Connecting Supertrees (IOI20_supertrees)C++14
0 / 100
1 ms212 KiB
#include "supertrees.h" #include <vector> #include <cassert> #include <numeric> using namespace std; template <typename T> bool operator==(vector<T> &a, vector<T> &b){ for (int i = 0; i < a.size(); ++i) { if (a[i] != b[i]) return false; } return true; } template <typename T> bool operator!=(vector<T> &a, vector<T> &b){ return !(a==b); } struct Unionfind { vector<int> group; Unionfind(int n) { group.resize(n); iota(group.begin(), group.end(), 0); } int find(int i){ if (group[i] == i) return i; return group[i] = find(group[i]); } void merge(int a, int b){ a = find(a); b = find(b); if (a == b) return; group[b] = group[a]; } }; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> res (n); vector<bool> inc (n); Unionfind unionfind (n); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] != 0) unionfind.merge(i, j); } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if ((p[i][j] == 0) && (unionfind.find(i) == unionfind.find(j))) return 0; } } for (int i = 0; i < n; ++i) { if (!res[i].empty()) continue; res[i].assign(n, 0); inc[i] = true; for (int j = 0; j < n; ++j) { if (p[i][j] == 0 || i == j) continue; if (p[i][j] == 1){ if (p[i] != p[j]) return 0; res[j].assign(n, 0); res[j][i] = 1; res[i][j] = 1; } } } for (int i = 0; i < n; ++i) { if (!inc[i]) continue; int ft = -1, lt = -1, bt = -1, at = -1; for (int j = 0; j < n; ++j) { if (inc[j]){ if (p[i][j] != 2) return 0; if (ft == -1) ft = j; if (j < i) bt = j; if (j > i && at == -1) at = j; lt = j; } } if (lt == -1) continue; if (at == -1) at = ft; if (bt == -1) bt = lt; res[i][bt] = 1; res[i][at] = 1; } build(res); return 1; }

Compilation message (stderr)

supertrees.cpp: In instantiation of 'bool operator==(std::vector<T>&, std::vector<T>&) [with T = int]':
supertrees.cpp:18:15:   required from 'bool operator!=(std::vector<T>&, std::vector<T>&) [with T = int]'
supertrees.cpp:64:32:   required from here
supertrees.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < a.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...