oj.uz

Submission #990121

# Submission time Handle Problem Language Result Execution time Memory
990121 2024-05-29T16:28:36 Z coftochka Bosses (BOI16_bosses) C++17
100 / 100
 494 ms 856 KB 
#include <bits/stdc++.h>

#define nl '\n'

signed main()
{
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> employee(n);

    for (int i = 0; i < n; i++)
    {
        int k;
        std::cin >> k;
        for (int j = 0; j < k; j++)
        {
            int x;
            std::cin >> x;
            --x;
            employee[x].push_back(i);
        }
    }
    int res = 1e9;

    for (int r = 0; r < n; r++)
    {
        std::vector<int> dep(n, -1);
        // now what can we do
        std::queue<int> q;
        q.push(r);
        dep[r] = 1;
        int ans = 1;
        int cnt = 0;
        while (q.size())
        {
            int u = q.front();
            q.pop();
            cnt++;

            for (int v : employee[u])
            {
                if (dep[v] == -1)
                {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                    ans += dep[v];
                }
            }
        }

        if (cnt == n)
        {
            res = std::min(ans, res);
        }
    }

    std::cout << res << nl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 432 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Correct 65 ms 652 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 404 ms 740 KB Output is correct
17 Correct 491 ms 604 KB Output is correct
18 Correct 494 ms 856 KB Output is correct