Submission #851190

#	Time	Username	Problem	Language	Result	Execution time	Memory
851190		antonio2006	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	604 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int dim=5005;
int n;
bool viz[dim];
int t[dim],d[dim],cost[dim];
vector<int> w[dim],f[dim],niv[dim];
void genarb(int nod){
    for(int i=1;i<=n;i++){
        f[i].clear();
        niv[i].clear();
    }
    for(int i=1;i<=n;i++){
        viz[i]=0;
        t[i]=0;
        d[i]=0;
    }
    d[nod]=1;
    niv[1].push_back(nod);
    queue<int> Q;
    viz[nod]=1;
    Q.push(nod);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=0;i<w[x].size();i++){
            int u=w[x][i];
            if(!viz[u]){
                t[u]=x;
                viz[u]=1;
                Q.push(u);
                d[u]=d[x]+1;
                niv[d[u]].push_back(u);
                f[x].push_back(u);

            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            w[x].push_back(i);
        }
    }
    int sol=1e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cost[i]=0;
        }
        genarb(i);
        int nmx=0;
        for(int j=1;j<=n;j++){
            nmx=max(nmx,d[j]);
        }
        for(int nc=nmx;nc>=1;nc--){
            for(auto x:niv[nc]){
                int sum=0;
                for(auto y:f[x]){
                    sum+=cost[y];
                }
                cost[x]=sum+1;
            }
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=cost[i];
        }
        sol=min(sol,sum);
    }
    cout<<sol;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void genarb(int)':
bosses.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i=0;i<w[x].size();i++){
      |                     ~^~~~~~~~~~~~

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