제출 #1263073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263073		rtri	Bosses (BOI16_bosses)	C++20	100 / 100	433 ms	1040 KiB

bosses

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

int main() {
  int n;
  cin >> n;

  vector<vector<int>> valid_bosses(n);
  vector<vector<int>> children(n);
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int idx;
      cin >> idx;
      idx--;
      valid_bosses[i].push_back(idx);
      children[idx].push_back(i);
    }
  }

  int res = 1e9;
  for (int root = 0; root < n; root++) {
    vector<int> par(n, -2);
    vector<int> ordering;

    deque<int> que;
    que.push_back(root);
    par[root] = -1;
    while (que.size()) {
      int node = que.front();
      que.pop_front();
      ordering.push_back(node);
      for (int cand : children[node])
        if (par[cand] == -2) {
          par[cand] = node;
          que.push_back(cand);
        }
    }

    if (ordering.size() != n)
      continue;

    reverse(ordering.begin(), ordering.end());

    vector<int> salary(n, 1);
    for (int elem : ordering)
      if (0 <= par[elem])
        salary[par[elem]] += salary[elem];

    int score = 0;
    for (int i = 0; i < n; i++)
      score += salary[i];

    res = min(res, score);
  }

  cout << res << endl;

  return 0;
}

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