Submission #208063

#	Time	Username	Problem	Language	Result	Execution time	Memory
208063		kai824	Bosses (BOI16_bosses)	C++17	0 / 100	5 ms	376 KiB

bosses

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

int dist[5005];
vector<int> children[5005];

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    queue<int> bfs;
    int n,k,a,maxi,ans=INT_MAX,cur;
    bool broke;
    cin>>n;
    for(int x=1;x<=n;x++){
      cin>>k;
      while(k--){
        cin>>a;
        children[a].push_back(x);
      }
    }

    for(int x=1;x<=n;x++){
      for(int i=1;i<=n;i++)dist[i]=INT_MAX;
      bfs.push(x);dist[x]=cur=maxi=0;
      while(!bfs.empty()){
        a=bfs.front();
        bfs.pop();
        for(int i=0;i<children[a].size();i++){
          if(dist[children[a][i]]==INT_MAX){
            dist[children[a][i]]=dist[a]+1;
            maxi=max(maxi,dist[a]+1);
            bfs.push(children[a][i]);
          }
        }
      }
      maxi++;
      broke=false;
      for(int i=1;i<=n;i++){
        if(dist[i]==INT_MAX){
          broke=true;
          break;
        }
        cur+=maxi-dist[i];
      }
      if(broke)continue;
      ans=min(ans,cur);
    }
    cout<<ans<<'\n';
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int32_t main()':
bosses.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<children[a].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~

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