oj.uz

Submission #69791

# Submission time Handle Problem Language Result Execution time Memory
69791 2018-08-21T13:41:15 Z Bodo171 Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 21208 KB 
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
const int nmax=5005;
int ad[nmax][nmax];
int q[nmax],d[nmax],nr[nmax];
int n,m,i,j,a,b,p,u,start,x,nod,k;
long long ans;
long long bfs()
{
    q[u=1]=start;
    d[start]=1;
    for(p=1;p<=u;p++)
    {
        x=q[p];
        for(i=1;i<=nr[x];i++)
        {
            nod=ad[x][i];
            if(!d[nod])
                d[nod]=d[x]+1,q[++u]=nod;
        }
    }
    long long ret=0;
    bool busit=0;
    for(i=1;i<=n;i++)
    {
        ret+=1LL*d[i];
        if(!d[i]) busit=1;
        d[i]=0;
    }
    if(busit) return LLONG_MAX;
    return ret;
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>k;
        for(j=1;j<=k;j++)
            {
                cin>>x;
                ad[x][++nr[x]]=i;
            }
    }
    ans=LLONG_MAX;
    for(start=1;start<=n;start++)
        ans=min(ans,bfs());
    cout<<ans;
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 636 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 796 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 4 ms 964 KB Output is correct
11 Correct 4 ms 1096 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 796 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 4 ms 964 KB Output is correct
11 Correct 4 ms 1096 KB Output is correct
12 Correct 12 ms 1516 KB Output is correct
13 Correct 12 ms 1516 KB Output is correct
14 Correct 195 ms 11076 KB Output is correct
15 Correct 37 ms 11112 KB Output is correct
16 Correct 957 ms 17548 KB Output is correct
17 Execution timed out 1571 ms 21208 KB Time limit exceeded
18 Halted 0 ms 0 KB -