Submission #446750

#	Time	Username	Problem	Language	Result	Execution time	Memory
446750		prvocislo	Bosses (BOI16_bosses)	C++17	100 / 100	802 ms	708 KiB

bosses

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int> > g(n);
    for (int i = 0; i < n; i++)
    {
        int d; cin >> d;
        for (int j = 0, x; j < d; j++)
        {
            cin >> x;
            g[--x].push_back(i);
        }
    }
    int ans = inf;
    for (int i = 0; i < n; i++)
    {
        queue<int> q; q.push(i);
        vector<int> d(n, inf); d[i] = 1;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int v : g[u]) if (d[v] == inf) d[v] = d[u]+1, q.push(v);
        }
        if (count(d.begin(), d.end(), inf)) continue;
        int sum = 0;
        for (int j = 0; j < n; j++) sum += d[j];
        ans = min(ans, sum);
    }
    cout << ans << "\n";
    return 0;
}

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