제출 #969986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969986		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	483 ms	856 KiB

bosses

/*
 * With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
 * TASK : Bossa Nova
 * AUTHOR : Marszpace
*/

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

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> adj(n+1,vector<int>());
  for(int i=1;i<=n;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int v;
      cin >> v;
      adj[v].push_back(i);
    }
  }

  int res=LLONG_MAX;
  queue<pair<int,int>> bfs;
  for(int root=1;root<=n;root++){
    bool visited[5001]={}; 
    int cnt=0; int thisres=0;
    
    visited[root]=true;
    bfs.push({root,1});
    while(!bfs.empty()){
      auto [u,c]=bfs.front();bfs.pop();
      cnt++;
      thisres+=c;
      for(auto &v:adj[u]){
        if(!visited[v]){
          visited[v]=true;
          bfs.push({v,c+1});
        }
      }
    }
    if(cnt==n){res=min(res,thisres);}
  }

  cout << res;
  return 0;
}

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