Submission #245803

#	Time	Username	Problem	Language	Result	Execution time	Memory
245803		uacoder123	Bosses (BOI16_bosses)	C++14	100 / 100	758 ms	760 KiB

bosses

 #include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
vi al[5001];
int t=0;
int bfs(int node)
{
  int vis[5001]={},ans=1,l=2;
  queue<int> q1,q2;
  q1.push(node);
  t++;
  vis[node]=1;
  while(q1.size())
  {
    int f=q1.front();
    for(int i=0;i<al[f].size();++i)
    {
      if(!vis[al[f][i]])
      {
        vis[al[f][i]]=1;
        ans+=l;
        q2.push(al[f][i]);
        t++;
      }
    }
    q1.pop();
    if(q1.size()==0)
    {
      swap(q1,q2);
      l++;
    }
  }
  return(ans);
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int test=1;
  for(;test>0;--test)
  {
    int n,ans=100000000;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
      int f,s;
      cin>>f;
      for(int j=0;j<f;++j)
      {
        cin>>s;
        al[s].pb(i);
      }
    }
    for(int i=1;i<=n;++i)
    {
      t=0;
      int pans=bfs(i);
      if(t==n)
        ans=min(ans,pans);
    }
    cout<<ans<<endl;
  }
  return(0);
}

Compilation message (stderr)

bosses.cpp: In function 'int bfs(int)':
bosses.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<al[f].size();++i)
                 ~^~~~~~~~~~~~~

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