Submission #765521

#	Time	Username	Problem	Language	Result	Execution time	Memory
765521		nguyen31hoang08minh2003	Bosses (BOI16_bosses)	C++17	100 / 100	417 ms	960 KiB

bosses

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

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<class X, class Y>
bool maximize(X &x, const Y &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

/**

    Every vertex would contrite to total cost
        a value equal to distance between it and the root of the tree
    => Minimize height
    => BFS

**/

constexpr int MAX_N = 5003, INF = 0X3F3F3F3F;

int n, result = INF, k[MAX_N], d[MAX_N];
vector<int> bosses[MAX_N], e[MAX_N];

int BFS(const int r) {
    int cost = 0, s = 0;
    queue<int> q;

    for (int u = 1; u <= n; ++u)
        d[u] = INF;

    q.push(r);
    d[r] = 1;

    for (; !q.empty(); q.pop()) {
        const int &u = q.front();
        cost += d[u];
        ++s;
        for (const int &v : e[u])
            if (minimize(d[v], d[u] + 1))
                q.push(v);
    }

    if (s != n)
        return INF;

    return cost;
}

signed main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
//        freopen("log.TXT", "w", stderr);
//        freopen("output.out", "w", stdout);
    #endif
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
        bosses[i].resize(k[i]);
        for (int &boss : bosses[i]) {
            cin >> boss;
            e[boss].push_back(i);
        }
    }

    for (int r = 1; r <= n; ++r)
        minimize(result, BFS(r));

    cout << result << '\n';

    return 0;
}

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