Submission #1271492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271492		lucaski2	Bosses (BOI16_bosses)	C++17	67 / 100	1596 ms	1104 KiB

bosses

#include <bits/stdc++.h>

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define f first 
#define s second

using namespace std;

const char en = '\n';



void solve(int tc)
{
  int n;
  cin >> n;

  vector<vector<int>> a(n);
  
  for (int i = 0; i < n; i++)
  {
    int k;
    cin >> k;
    while (k--)
    {
      int c;
      cin >> c;
      c--;
      a[c].push_back(i);
    }
  }
  int ans = INT_MAX;
  vector<bool> visited(n);
  vector<vector<int>> graph(n);
  for (int r = 0; r < n; r++)
  {
    

    bitset<5005> visited;
    vector<vector<int>> graph(n);

    queue<int> q;
    q.push(r);
    visited[r] = true;
    int cnt = 0;
    while (q.size())
    {
      cnt++;
      int cur = q.front();
      q.pop();

      for (int neigh : a[cur])
      {
        if (visited[neigh]) continue;
        graph[cur].push_back(neigh);
        q.push(neigh);
        visited[neigh] = true;
      }
    }
    if (cnt < n) continue;
    int ret = 0;
    function<int(int)> dfs = [&](int cur)
    {
      int tot = 1;
      // cout << cur << endl;
      for (int neigh : graph[cur])
      {
        tot += dfs(neigh);
      }
      ret += tot;
      return tot;
    };
    dfs(r);
    ans = min(ret, ans);
  }

  cout << ans << en;
}

signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  for (int i = 1; i <= t; i++)
  {
    solve(i);
  }
}

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