Submission #140250

#	Time	Username	Problem	Language	Result	Execution time	Memory
140250		path	Bosses (BOI16_bosses)	C++14	100 / 100	1084 ms	760 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long int ll;
const int N=5e3+5;
int n,k,t,c,vis[N];
ll ans,cst;
vector <int> al[N];
int BFS(int ind){
    queue < pair<int,int> > q;
    q.push(make_pair(ind,1));
    vis[ind]=1;
    pair<int,int> tmp;
    while(q.size()){
        tmp=q.front();
        q.pop();
        cst+=tmp.s;
        c++;
        for(int i=0;i<al[tmp.f].size();i++){
            if(vis[al[tmp.f][i]]) continue;
            vis[al[tmp.f][i]]=1;
            q.push(make_pair(al[tmp.f][i],tmp.s+1));
        }
    }
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>k;
        while(k--){
            cin>>t;
            al[t].push_back(i+1);
        }
    }
    ans=N*N*N;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        c=cst=0;
        BFS(i);
        if(c==n)
            ans=min(ans,cst);
    }
    cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int BFS(int)':
bosses.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<al[tmp.f].size();i++){
                     ~^~~~~~~~~~~~~~~~~
bosses.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
bosses.cpp: In function 'int main()':
bosses.cpp:38:12: warning: integer overflow in expression [-Woverflow]
     ans=N*N*N;
         ~~~^~

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