Submission #505105

#	Time	Username	Problem	Language	Result	Execution time	Memory
505105		erke	Bosses (BOI16_bosses)	C++11	100 / 100	1437 ms	1048 KiB

bosses

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

const int N = 5005;

vector<int> adj[N], adj_tmp[N];
int sum = 0;

int dfs(int i) {
  int ret = 1;
  for (auto &j : adj_tmp[i]) {
    ret += dfs(j);
  }
  sum += ret;
  return ret;
}

int main() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    int k; cin >> k;
    for (int j = 1; j <= k; j++) {
      int x; cin >> x;
      adj[x].push_back(i);
    }
  }
  int ans = INT_MAX;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      adj_tmp[j].clear();
    }
    queue<pair<int,int>> q; q.push({i, 0});
    vector<int> vst(n + 1);
    while (q.size()) {
      auto i = q.front(); q.pop();
      if (vst[i.first]) continue;
      vst[i.first] = 1;
      adj_tmp[i.second].push_back(i.first);
      for (auto &j : adj[i.first]) {
        q.push({j, i.first});
      }
    }
    bool flag = false;
    for (int j = 1; j <= n; j++) {
      if (!vst[j]) {
        flag = true;
        break;
      }
    }
    if (!flag) {
      sum = 0;
      dfs(i);
      ans = min(ans, sum);
    }
  }
  cout << ans << '\n';
}

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