Submission #79526

#	Time	Username	Problem	Language	Result	Execution time	Memory
79526		IOrtroiii	Bosses (BOI16_bosses)	C++14	100 / 100	666 ms	888 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;

int n;
vector<int> g[N];
int F[N];

long long bfs(int root) {
   for (int i = 1; i <= n; ++i) F[i] = 0;
   long long sum = 0;
   int cnt = 0;
   queue<int> q; q.push(root);
   F[root] = 1;
   while (!q.empty()) {
      int u = q.front(); q.pop();
      sum += F[u]; cnt++;
      for (int v : g[u]) if (F[v] == 0) {
         F[v] = F[u] + 1;
         q.push(v);
      }
   }
   if (cnt < n) return 1e18;
   return sum;
}

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i) {
      int x; scanf("%d", &x);
      while (x--) {
         int u; scanf("%d", &u);
         g[u].push_back(i);
      }
   }
   long long res = 1e18;
   for (int i = 1; i <= n; ++i) res = min(res, bfs(i));
   cout << res << '\n';
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
bosses.cpp:31:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int x; scanf("%d", &x);
              ~~~~~^~~~~~~~~~
bosses.cpp:33:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          int u; scanf("%d", &u);
                 ~~~~~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33