제출 #1231791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231791		chikien2009	Bosses (BOI16_bosses)	C++20	100 / 100	395 ms	736 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b, c, f[5000], m;
vector<int> g[5000];
deque<int> dq;

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        while (a--)
        {
            cin >> b;
            g[b - 1].push_back(i);
        }
    }
    c = 1e9;
    for (int i = 0; i < n; ++i)
    {
        fill_n(f, 5000, 1e9);
        f[i] = 1;
        dq = {i};
        b = m = 0;
        while (!dq.empty())
        {
            m++;
            a = dq.front();
            b += f[a];
            dq.pop_front();
            for (auto &i : g[a])
            {
                if (f[i] == 1e9)
                {
                    f[i] = f[a] + 1;
                    dq.push_back(i);
                }
            }
        }
        if (m == n)
        {
            c = min(b, c);
        }
    }
    cout << c;
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33