oj.uz

Submission #78542

# Submission time Handle Problem Language Result Execution time Memory
78542 2018-10-06T07:37:57 Z vex Bosses (BOI16_bosses) C++14
100 / 100
 674 ms 1020 KB 
#include <bits/stdc++.h>
#define maxn 5005
#define INF int(1e9+233)
using namespace std;

int n;
vector<int>d[maxn];
bool bio[maxn];

int dub[maxn];
queue<int>mq;
int bfs(int v)
{
    mq.push(v);
    for(int i=1;i<=n;i++)
    {
        dub[i]=-1;
        bio[i]=false;
    }
    bio[v]=true;
    dub[v]=1;
    int tre=1;
    int br=1;
    while(!mq.empty())
    {
        int u=mq.front();
        mq.pop();

        for(auto x:d[u])
        {
            if(bio[x])continue;
            mq.push(x);
            bio[x]=true;
            br++;
            dub[x]=dub[u]+1;
            tre+=dub[x];
        }
    }

    if(br<n)return INF;
    return tre;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        for(int j=0;j<x;j++)
        {
            int w;
            cin>>w;
            d[w].push_back(i);
        }
    }

    int sol=INF;
    for(int i=1;i<=n;i++)sol=min(sol,bfs(i));
    cout<<sol<<endl;
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 2 ms 788 KB Output is correct
6 Correct 2 ms 788 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 2 ms 788 KB Output is correct
6 Correct 2 ms 788 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 884 KB Output is correct
10 Correct 2 ms 884 KB Output is correct
11 Correct 2 ms 884 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 2 ms 788 KB Output is correct
6 Correct 2 ms 788 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 884 KB Output is correct
10 Correct 2 ms 884 KB Output is correct
11 Correct 2 ms 884 KB Output is correct
12 Correct 6 ms 884 KB Output is correct
13 Correct 5 ms 884 KB Output is correct
14 Correct 166 ms 884 KB Output is correct
15 Correct 37 ms 892 KB Output is correct
16 Correct 619 ms 1020 KB Output is correct
17 Correct 671 ms 1020 KB Output is correct
18 Correct 674 ms 1020 KB Output is correct