Submission #1271490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271490		lucaski2	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	328 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++)
  {
    

    vector<bool> visited(n);
    vector<vector<int>> graph(n);

    vector<int> q(n);
    int ptr = 0;
    int ptr2 = 0;

    q[ptr2++] = r;
    visited[r] = true;
    int cnt = 0;
    while (ptr < n)
    {
      cnt++;
      int cur = q[ptr++];

      for (int neigh : a[cur])
      {
        if (visited[neigh]) continue;
        graph[cur].push_back(neigh);
        q[ptr2++] = 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: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33