Submission #851183

#	Time	Username	Problem	Language	Result	Execution time	Memory
851183		antonio2006	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	344 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];
vector<int> w[dim];
void genarb(int nod){
    for(int i=1;i<=n;i++){
        viz[i]=0;
        t[i]=0;
    }
    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);
            }
        }
    }
}
int calcsum(int nod){
    for(int i=1;i<=n;i++){
        d[i]=0;
        viz[i]=0;
    }
    viz[nod]=1;
    queue<int> Q;
    Q.push(nod);
    int s=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=1;i<=n;i++){
            if(t[i]==x and !viz[i]){
                viz[i]=1;
                Q.push(i);
                d[i]=d[x]+1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        s+=d[i];
    }
    return s+n;
}
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++){
        genarb(i);
        sol=min(sol,calcsum(i));
    }
    cout<<sol;
    return 0;
}

Compilation message (stderr)

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

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