oj.uz

Submission #32264

# Submission time Handle Problem Language Result Execution time Memory
32264 2017-10-05T14:01:50 Z dqhungdl Bosses (BOI16_bosses) C++14
100 / 100
 653 ms 2464 KB 
#include <bits/stdc++.h>
using namespace std;

int n,res=1e9,h[5005],Q[5005];
vector<int> g[5005];

void BFS(int u)
{
    for(int i=1;i<=n;i++)
        h[i]=0;
    h[u]=1;
    Q[1]=u;
    int l=1,r=1;
    while(l<=r)
    {
        int u=Q[l++];
        for(int i=0;i<g[u].size();i++)
            if(h[g[u][i]]==0)
            {
                Q[++r]=g[u][i];
                h[g[u][i]]=h[u]+1;
            }
    }
    if(r==n)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
            sum+=h[i];
        res=min(res,sum);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("BOSSES.INP","r",stdin);
    cin>>n;
    int k,x;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        while(k--)
        {
            cin>>x;
            g[x].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
        BFS(i);
    cout<<res;
}

Compilation message

bosses.cpp: In function 'void BFS(int)':
bosses.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[u].size();i++)
                      ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 0 ms 2332 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2332 KB Output is correct
5 Correct 0 ms 2332 KB Output is correct
6 Correct 0 ms 2332 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 0 ms 2332 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2332 KB Output is correct
5 Correct 0 ms 2332 KB Output is correct
6 Correct 0 ms 2332 KB Output is correct
7 Correct 0 ms 2332 KB Output is correct
8 Correct 0 ms 2332 KB Output is correct
9 Correct 0 ms 2332 KB Output is correct
10 Correct 0 ms 2332 KB Output is correct
11 Correct 0 ms 2332 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 0 ms 2332 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2332 KB Output is correct
5 Correct 0 ms 2332 KB Output is correct
6 Correct 0 ms 2332 KB Output is correct
7 Correct 0 ms 2332 KB Output is correct
8 Correct 0 ms 2332 KB Output is correct
9 Correct 0 ms 2332 KB Output is correct
10 Correct 0 ms 2332 KB Output is correct
11 Correct 0 ms 2332 KB Output is correct
12 Correct 3 ms 2332 KB Output is correct
13 Correct 3 ms 2332 KB Output is correct
14 Correct 133 ms 2332 KB Output is correct
15 Correct 13 ms 2332 KB Output is correct
16 Correct 589 ms 2464 KB Output is correct
17 Correct 653 ms 2464 KB Output is correct
18 Correct 636 ms 2464 KB Output is correct