oj.uz

Submission #349309

# Submission time Handle Problem Language Result Execution time Memory
349309 2021-01-17T11:30:29 Z iANikzad Bosses (BOI16_bosses) C++14
100 / 100
 781 ms 876 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 5e3 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

vector<int> adj[maxn];
int mark[maxn], dis[maxn];

int n;

int bfs(int root)
{
    queue<int> q;

    for(int i=1;i<=n;i++) mark[i] = dis[i] = 0;

    q.push(root);
    mark[root] = 1;
    dis[root] = 1;

    while(!q.empty())
    {
        int v = q.front();
        q.pop();

        for(int u : adj[v])
        {
            if(mark[u]) continue;

            mark[u] = true;
            dis[u] = dis[v] + 1;
            q.push(u);
        }
    }

    int res = 0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i] == 0) return +INF;
        res += dis[i];
    }

    return res;
}

int32_t main()
{
    FAST;

    cin >> n;

    for(int i=1;i<=n;i++)
    {
        int k;
        cin >> k;

        for(int j=1;j<=k;j++)
        {
            int boss;
            cin >> boss;

            adj[boss].pb(i);
        }
    }

    int ans = +INF;
    for(int i=1;i<=n;i++)
    {
        int res = bfs(i);
        ans = min(ans, res);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 149 ms 748 KB Output is correct
15 Correct 27 ms 620 KB Output is correct
16 Correct 597 ms 748 KB Output is correct
17 Correct 756 ms 876 KB Output is correct
18 Correct 781 ms 748 KB Output is correct