제출 #789808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789808		makanhulia	Bosses (BOI16_bosses)	C++17	100 / 100	389 ms	616 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
using namespace std;
vector<ll> adj[5010];

int main(){
  int n; cin >> n;
  for(int i=1; i<=n; i++){
    int k; cin >> k;
    for(int j=0; j<k; j++){
      int a; cin >> a;
      adj[a].pb(i); // k bisa jadi child dr a
    }
  }
  ll ans=100000000;
  for(int i=1; i<=n; i++){ //nyobain satu satu yg jd root nya
    int depth[5010]; memset(depth, 0, sizeof(depth));
    bool vis[5010]; memset(vis, 0, sizeof(vis));
    int lvl[5010]; memset(lvl, 0, sizeof(lvl));
    queue<int> q;
    q.push(i);
    vis[i]=1; depth[1]=1; lvl[i]=1;
    int batas=1;
    while(!q.empty()){
    int cur = q.front(); q.pop();
      for(auto j : adj[cur]){
        if(vis[j]) continue;
        lvl[j]=lvl[cur]+1; batas=max(batas, lvl[j]);
        depth[lvl[j]]++;
        vis[j]=1; 
        q.push(j);
      }
    }
    bool bisa=1;
    for(auto i=1; i<=n; i++){
      if(!vis[i]){
        bisa=0; break;
      }
    }
    if(!bisa) continue;
    ll sum[batas+10], total=0;
    sum[batas+1]=0;
    for(int i=batas; i>=1; i--){
      sum[i]=depth[i]+sum[i+1];
      total +=sum[i];
    }
    ans=min(ans, total);
  }
  cout << ans << endl;
  return 0;
}

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