Submission #208076

#	Time	Username	Problem	Language	Result	Execution time	Memory
208076		kai824	Bosses (BOI16_bosses)	C++17	67 / 100	1595 ms	892 KiB

bosses

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

bool vis[5005];
int cur,nodes;
vector<int> children[5005],children2[5005];

inline int dfs(int x){//returns salary of employee x...
  nodes++;
  int ans=1;
  for(int i=0;i<children2[x].size();i++){
    ans+=dfs(children2[x][i]);
  }
  cur+=ans;
  return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    queue<int> bfs;
    int n,k,a,ans=INT_MAX;
    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++){vis[i]=0;children2[i].clear();}
      bfs.push(x);vis[x]=1;
      nodes=0;
      while(!bfs.empty()){
        nodes++;
        a=bfs.front();
        bfs.pop();
        for(int i=0;i<children[a].size();i++){
          if(!vis[children[a][i]]){
            vis[children[a][i]]=true;
            bfs.push(children[a][i]);
            children2[a].push_back(children[a][i]);
          }
        }
      }
      if(nodes!=n)continue;
      cur=0;
      dfs(x);
      ans=min(ans,cur);
    }
    cout<<ans<<'\n';
    return 0;
}

Compilation message (stderr)

bosses.cpp:4:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
bosses.cpp: In function 'int dfs(int)':
bosses.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<children2[x].size();i++){
               ~^~~~~~~~~~~~~~~~~~~~
bosses.cpp: In function 'int32_t main()':
bosses.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<children[a].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~
bosses.cpp:27:10: warning: unused variable 'broke' [-Wunused-variable]
     bool broke;
          ^~~~~

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