제출 #990121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990121		coftochka	Bosses (BOI16_bosses)	C++17	100 / 100	494 ms	856 KiB

bosses

#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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33