Submission #279668

#	Time	Username	Problem	Language	Result	Execution time	Memory
279668		erray	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	384 KiB

bosses

// author: erray
#include<bits/stdc++.h>
 
using namespace std;
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int x;
      cin >> x;
      --x;
      g[x].push_back(i);
    }
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < n; ++i) {
    vector<bool> vis(n);
    vector<long long> val(n, 1);
    function<long long(int)> dfs = [&](int v) {
      vis[v] = true;
      for (auto u : g[v]) {
        if (vis[u]) continue;
        val[v] += dfs(u); 
      }
      return val[v];
    };
    dfs(i); 
    ans = min(ans, accumulate(val.begin(), val.end(), 0LL));
  }
  cout << ans << '\n';
}

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