제출 #981063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981063		kilkuwu	Bosses (BOI16_bosses)	C++17	100 / 100	434 ms	792 KiB

bosses

#include <bits/stdc++.h>

#define nl '\n'

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n;
  std::cin >> n;
  std::vector<std::vector<int>> employee(n);

  for (int i = 0; i < n; i++) {
    int k;
    std::cin >> k;
    for (int j = 0; j < k; j++) {
      int x; std::cin >> x;
      --x;
      employee[x].push_back(i);
    }
  }
  int res = 1e9;

  for (int r = 0; r < n; r++) {
    std::vector<int> dep(n, -1);
    // now what can we do 
    std::queue<int> q;
    q.push(r);
    dep[r] = 1;
    int ans = 1;
    int cnt = 0;
    while (q.size()) {
      int u = q.front();
      q.pop();
      cnt++;

      for (int v : employee[u]) {
        if (dep[v] == -1) {
          dep[v] = dep[u] + 1;
          q.push(v);
          ans += dep[v];
        }
      }
    }

    if (cnt == n) {
      res = std::min(ans, res);
    }
  }

  std::cout << res << nl;
}

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