Submission #1209054

#TimeUsernameProblemLanguageResultExecution timeMemory
1209054badge881Bosses (BOI16_bosses)C++20
100 / 100
772 ms1012 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> baseListAdj, listAdj; pair<int, int> dfs(int x) { int ans = 0, sm = 1; for (auto v : listAdj[x]) { auto [ansi, smi] = dfs(v); ans += ansi, sm += smi; } ans += sm; return {ans, sm}; } signed main() { int n; scanf("%d", &n); baseListAdj.resize(n), listAdj.resize(n); vector<int> cnt(n); for (int i = 0; i < n; i++) { int k; scanf("%d", &k); for (int j = 0; j < k; j++) { int x; scanf("%d", &x); x--; baseListAdj[x].push_back(i); } } int ans = n * n; for (int t = 0; t < n; t++) { queue<int> q; q.push(t); vector<int> dist(n, 0); vector<bool> visited(n, 0); visited[t] = 1; for (auto &u : listAdj) u.clear(); while (!q.empty()) { int u = q.front(); q.pop(); for (auto v : baseListAdj[u]) if (!visited[v]) { dist[v] = dist[u] + 1, visited[v] = 1; q.push(v); listAdj[u].push_back(v); } } bool ok = 1; for (int i = 0; i < n; i++) if (!visited[i]) ok = 0; if (!ok) continue; ans = min(ans, dfs(t).first); } printf("%d\n", ans); }

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
bosses.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
bosses.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...