Submission #532262

#	Time	Username	Problem	Language	Result	Execution time	Memory
532262		andecaandeci	Bosses (BOI16_bosses)	C++17	100 / 100	637 ms	800 KiB

bosses

#include <bits/stdc++.h>
#define REP(v, i, j) for (int v = i; v < j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)

#define OUT(v, a)     FORI(v)           cout << i << a;
#define OUTS(v, a, b)          cout << v.size() << a;     OUT(v, b)
#define in(a, n)     REP(i, 0, n)     cin >> a[i];

#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))

#define pb push_back
#define fi first
#define se second

#define detachIO                          ios_base::sync_with_stdio(false);     cin.tie(0);                           cout.tie(0);

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> piiii;

vector<int> child[10000];
int dist[10000];

int n;

int bfs(int root)
{
    memset(dist, -1, sizeof dist);

    queue<pii> q;
    q.push({root, 0});

    while (q.size())
    {
        auto &x = q.front();
        q.pop();

        if (dist[x.fi] != -1)
            continue;

        dist[x.fi] = x.se;

        FORI(child[x.fi])
        q.push({i, x.se + 1});
    }

    REP(j, 0, n)
    if (dist[j] == -1)
        return -1;
    return 0;
}

int main()
{
    detachIO;

    cin >> n;

    REP(i, 0, n)
    {
        int x;
        cin >> x;

        while (x--)
        {
            int t;
            cin >> t;
            t--;

            child[t]
                .pb(i);
        }
    }

    int finalres = INT_MAX;

    REP(i, 0, n)
    {
        if (bfs(i))
            continue;

        int ans = 0;
        REP(j, 0, n)
        ans += dist[j];
        ans += n;

        finalres = min(finalres, ans);
    }

    cout << finalres << '\n';
}

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