Submission #857776

#	Time	Username	Problem	Language	Result	Execution time	Memory
857776		qrno	Bosses (BOI16_bosses)	C++17	100 / 100	356 ms	848 KiB

bosses

#include <cstdio>
#include <vector>
#include <array>
#include <bitset>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int INF = 1e9;
const int MAXN = 5e3;

int best = INF;

int N;
array<vector<short>, MAXN> G;
array<short, MAXN> val, q;

signed main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    int K; scanf("%d", &K);
    while (K--) {
      int u; scanf("%d", &u); u--;
      G[u].push_back(i);
    }
  }

  for (int i = 0; i < N; i++) {
    int l = 0, r = -1;

    bitset<MAXN> vis;
    q[++r] = i;
    val[i] = 1;
    vis[i] = true;

    int done = 0, sum = 0;
    while (l <= r) {
      auto v = q[l++];
      sum += val[v];
      done++;
      for (auto u : G[v]) {
        if (!vis[u]) {
          q[++r] = u;
          val[u] = val[v]+1;
          vis[u] = true;
        }
      }
    }
    if (done < N) continue;

    best = min(best, sum);
  }

  printf("%d", best);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
bosses.cpp:22:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     int K; scanf("%d", &K);
      |            ~~~~~^~~~~~~~~~
bosses.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |       int u; scanf("%d", &u); u--;
      |              ~~~~~^~~~~~~~~~

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