Submission #1242495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242495		coderpemula	Bosses (BOI16_bosses)	C++20	100 / 100	663 ms	1028 KiB

bosses

//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

/* Some Makoto Shinkai's : 

  “Who cares if we can't see any sunshine? I want you more than any blue sky!!!”
    - Tenki no Ko
    
  "By the time the date is over, the comet will be visible in the sky."
    - Kimi no Nawa
    
  “No matter what happens, even if the stars fall, I will live.”
    - Byōsoku 5 Centimeter
  
*/
#include <bits/stdc++.h>
#define Raveluk ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define tii tuple<int,int,int>
#define g1 get<0>
#define g2 get<1>
#define g3 get<2>
#define qf q.front()
#define all(x) (x).begin(), (x).end()
using namespace std;
#define int long long
vector<int>v[5001],w[5001];
bool vis[5001];
int tem;
queue<int>q;
int dfs(int node, int par){
  if(w[node].empty()) return 1;
  ll temp = 0;
  for(auto x:w[node]){
    if(x != par){
      int cari = dfs(x,node);
      temp += cari;
      tem += cari;
    }
  }
  return temp+1;
}
signed main()
{
  Raveluk
  int n,i,j,k,x,ans=1e18;
  cin>>n;
  for(i=1;i<=n;i++){
    cin>>k;
    for(j=1;j<=k;j++){
      cin>>x;
      v[x].pb(i);
    }
  }
  for(i=1;i<=n;i++){
    // i sebagai root
    // maksimalkan child
    int node = i,cnt=0;
    q.push(i);
    tem = 0;
    for(j=1;j<=n;j++) vis[j] = false,w[j].clear();
    vis[i] = true;
    while(!q.empty()){
      q.pop();
      cnt++;
      for(auto x:v[node]){
        if(!vis[x]){
          vis[x] = true;
          w[node].pb(x);
          q.push(x);
        }
      }
      if(q.empty()) break;
      node = q.front();
    }
    if(cnt < n) continue;
    //cout<<i<<" "<<tem<<endl;
    ans = min(ans,dfs(i,0)+tem);
  }
  cout<<ans;
  
  return 0;
}

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