oj.uz

Submission #851191

# Submission time Handle Problem Language Result Execution time Memory
851191 2023-09-18T19:55:51 Z antonio2006 Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 604 KB 
#include <iostream>
#include <vector>
#include <queue>
#define int long long 
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);

            }
        }
    }
}
signed 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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -