Submission #580361

#TimeUsernameProblemLanguageResultExecution timeMemory
580361joelauConnecting Supertrees (IOI20_supertrees)C++14
19 / 100
212 ms24080 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int N,ufds[1005], rnk[1005]; vector<int> lst[1005]; int findSet(int i) { return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]); } void unionSet(int i, int j) { int a = findSet(i), b = findSet(j); if (a == b) return; if (rnk[a] < rnk[b]) ufds[a] = b; if (rnk[a] > rnk[b]) ufds[b] = a; if (rnk[a] == rnk[b]) ufds[a] = b, rnk[b]++; } int construct(vector<vector<int>> p) { N = p.size(); for (int i = 0; i < N; ++i) ufds[i] = i, rnk[i] = 1; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (p[i][j] == 2) unionSet(i,j); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (i != j) { if (p[i][j] == 2 && findSet(i) != findSet(j)) return 0; if (p[i][j] == 0 && findSet(i) == findSet(j)) return 0; } vector< vector<int> > ans(N, vector<int>(N,0)); for (int i = 0; i < N; ++i) lst[findSet(i)].push_back(i); for (int i = 0; i < N; ++i) { if (lst[i].size() == 2) return 0; if (lst[i].size() >= 3) { for (int j = 1; j < lst[i].size(); ++j) ans[lst[i][j-1]][lst[i][j]] = ans[lst[i][j]][lst[i][j-1]] = 1; ans[lst[i].front()][lst[i].back()] = ans[lst[i].back()][lst[i].front()] = 1; } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for (int j = 1; j < lst[i].size(); ++j) ans[lst[i][j-1]][lst[i][j]] = ans[lst[i][j]][lst[i][j-1]] = 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...