Submission #532243

#	Time	Username	Problem	Language	Result	Execution time	Memory
532243		kebine	Bosses (BOI16_bosses)	C++17	100 / 100	677 ms	632 KiB

bosses

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

typedef long long ll;
const ll mod = 1e9 + 7;
#pragma GCC optimize("Ofast")
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n, k, b, ans = INT_MAX;
vector<vi > bos(5002);

int main()
{
  cin >> n;
  
  for(int i = 1; i <= n; i++){
    cin >> k;
    while(k--){
      cin >> b;
      bos[b].pb(i);
    }
  }
  
  queue<int> q;
  vi nambah(n + 1, 0);
  
  for(int i = 1; i <= n; i++){
    vector<bool> vis(n + 1, 0);
    q.push(i);
    int cnt = 1;
    vis[i] = 1;
    nambah[i] = 1;
    
    while(!q.empty()){
      int cur = q.front(); q.pop();
      for(auto it : bos[cur])
        if(!vis[it]){
          vis[it] = 1;
          nambah[it] = nambah[cur] + 1;
          q.push(it);
          cnt++; 
        }
    }
    
    if(cnt != n) continue;
    int sum = 0;
    for(int i = 1; i <= n; i++)
      sum += nambah[i];
      
    ans = min(ans, sum);
  }
  
  cout << ans << endl;
}

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