Submission #329765

#	Time	Username	Problem	Language	Result	Execution time	Memory
329765		SuhaibSawalha1	Bosses (BOI16_bosses)	C++17	100 / 100	721 ms	752 KiB

bosses

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

int main (){
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int n;
  cin >> n;
  vector<vector<int>> adj(n);
  for (int u = 0; u < n; ++u){
    int k, v;
    cin >> k;
    while (k--){
      cin >> v;
      adj[--v].push_back(u);
    }
  }
  vector<int> visited(n, -1);
  int ans = 1e9;
  for (int i = 0; i < n; ++i){
    int vis = 0, cost = 0, cnt = 1;
    visited[i] = i;
    for (queue<int> q {{i}}; !q.empty(); ++cnt){
      int s = q.size();
      cost += s * cnt;
      vis += s;
      while (s--){
        int u = q.front();
        q.pop();
        for (int v : adj[u]){
          if (visited[v] ^ i){
            q.push(v);
            visited[v] = i;
          }
        }
      }
    }
    ans = min(ans, vis == n ? cost : ans);
  }
  cout << ans;

  return 0;
}

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