Submission #329297

#	Time	Username	Problem	Language	Result	Execution time	Memory
329297		NicolaAbusaad2014	Bosses (BOI16_bosses)	C++14	100 / 100	1038 ms	784 KiB

bosses

/**
 * Prof.Nicola
**/
#include <bits/stdc++.h>

using namespace std;
vector<vector<long> >edges;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long n,x,z;
    cin>>n;
    edges.resize(n+1);
    for(long i=0;i<n;i++){
        cin>>x;
        for(long j=0;j<x;j++){
            cin>>z;
            edges[z].push_back(i+1);
        }
    }
    long long ans=1e9;
    for(long i=1;i<=n;i++){
        queue<pair<long long,long> >pq;
        bool vis[n+1]={};
        vector<long long>best(n+1,-1e9);
        long long cost=0,m=0;
        pq.push(make_pair(0,i));
        while(!pq.empty()){
            z=pq.front().first;
            x=pq.front().second;
            pq.pop();
            if(!vis[x]){
                m++;
                cost+=-z+1;
                vis[x]=true;
                for(long j=0;j<edges[x].size();j++){
                    if(z-1>best[edges[x][j]]){
                        best[edges[x][j]]=z-1;
                        pq.push(make_pair(z-1,edges[x][j]));
                    }
                }
            }
        }
        if(m==n){
            ans=min(ans,cost);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:37:31: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 for(long j=0;j<edges[x].size();j++){
      |                              ~^~~~~~~~~~~~~~~~

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