Submission #208088

#	Time	Username	Problem	Language	Result	Execution time	Memory
208088		Blerargh	Bosses (BOI16_bosses)	C++17	67 / 100	1586 ms	4112 KiB

bosses

#include "bits/stdc++.h"
using namespace std;
 
#define int long long
 
bool vis[5005];
int n,k,a,ans=INT_MAX;
int preorder[5005],nex;
int cur,nodes;
vector<int> children[5005];
stack<int> children2[5005];
 
void dfs(int x){//returns salary of employee x...
  preorder[x]=nex++;
  while(!children2[x].empty()){
    a=children2[x].top();
    children2[x].pop();
    dfs(a);
  }
  cur+=nex-preorder[x];
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    queue<int> bfs;
    cin>>n;
    for(int x=1;x<=n;x++){
      cin>>k;
      while(k--){
        cin>>a;
        children[a].emplace_back(x);
      }
    }
 
    for(int x=1;x<=n;x++){
      for(int i=1;i<=n;i++){
        vis[i]=0;
        while(!children2[i].empty())children2[i].pop();
      }
      bfs.emplace(x);vis[x]=1;
      nodes=0;
      while(!bfs.empty()){
        nodes++;
        a=bfs.front();
        bfs.pop();
        for(auto edge : children[a]){
          if(!vis[edge]){
            vis[edge]=true;
            bfs.emplace(edge);
            children2[a].emplace(edge);
          }
        }
      }
      if(nodes!=n)continue;
      cur=0;
      nex=1;
      dfs(x);
      ans=min(ans,cur);
    }
    cout<<ans<<'\n';
    return 0;
}

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