Submission #79520

#	Time	Username	Problem	Language	Result	Execution time	Memory
79520		IOrtroiii	Bosses (BOI16_bosses)	C++14	67 / 100	1554 ms	1404 KiB

bosses

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

const int N = 5005;

int n;
vector<int> g[N];
vector<int> new_g[N];
vector<int> new_g2[N];
bool visit[N];
long long F[N];

void dfs(int u) {
   F[u] = 1;
   for (int v : new_g[u]) {
      dfs(v);
      F[u] += F[v];
   }
}

long long bfs(int root) {
   for (int i = 1; i <= n; ++i) {
      visit[i] = 0;
      new_g[i].clear();
   }
   queue<int> q;
   visit[root] = 1;
   q.push(root);
   while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : g[u]) {
         if (!visit[v]) {
            new_g[u].push_back(v);
            q.push(v);
            visit[v] = 1;
         }
      }
   }

   dfs(root);
   long long sum = 0;
   for (int i = 1; i <= n; ++i) {
      if (!visit[i]) return 1e18;
      sum += F[i];
   }
   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:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
bosses.cpp:52: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:54: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: 0 / 33