Submission #610325

#TimeUsernameProblemLanguageResultExecution timeMemory
610325jairRSConnecting Supertrees (IOI20_supertrees)C++17
11 / 100
201 ms23968 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; struct DSU{ vi p, s; DSU(int size){ p = s = vi(size + 1, 1); for(int i = 0; i <= size; i++) p[i] = i; } int find(int x){ if(p[x] == x) return x; return p[x] = find(p[x]); } void unite(int a, int b){ a = find(a); b = find(b); if(a == b) return; if(s[a] > s[b]) swap(a, b); s[b] += s[a]; p[a] = b; } }; int construct(vvi p) { int n = p.size(); vvi answer = vvi(n, vi(n, 0)); DSU dsu(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if(p[i][j]) dsu.unite(i, j); vvi group(n, vi()); for (int i = 0; i < n; i++) group[dsu.find(i)].push_back(i); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if(dsu.find(i) == dsu.find(j) && !p[i][j]) return 0; for(vi & g : group) for (int i = 0; i + 1 < g.size(); i++) { answer[i][i + 1] = 1; answer[i + 1][i] = 1; } build(answer); return 1; }

Compilation message (stderr)

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