Submission #329538

#	Time	Username	Problem	Language	Result	Execution time	Memory
329538		gustason	Bosses (BOI16_bosses)	C++14	67 / 100	1587 ms	1200 KiB

bosses

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

const int maxN = 5005;
const int INF = 1e9 + 5;
vector<int> adj[maxN];
int n;
int smallest_depth = maxN;

int solve(int root) {
    vector<int> dep[n+1]; // vertices that are at some depth
    vector<int> new_adj[n+1];
    vector<bool> conn(n+1, false); // is vertex already used
    conn[root] = true;
    dep[1].push_back(root);

    int cnt = 1, depth = 0;
    for(int d = 1; d < n; d++) {
        for(int v : dep[d]) {
            for(int u : adj[v]) {
                if (!conn[u]) {
                    new_adj[u].push_back(v);
                    dep[d+1].push_back(u);
                    conn[u] = true;
                    depth = d + 1;
                    if (depth > smallest_depth + (n / 2)) return INF;
                    cnt++;
                }
            }
        }
    }

    smallest_depth = min(smallest_depth, depth);
    if (cnt != n) return INF;
    vector<int> sal(n+1, 0);
    int sum = 0;
    for(int d = n; d >= 1; d--) {
        for(int ord : dep[d]) {
            sal[ord]++;
            sum += sal[ord];
            for(int boss : new_adj[ord]) {
                sal[boss] += sal[ord];
            }
        }
    }

    return sum;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int ord = 1; ord <= n; ord++) {
        int k;
        cin >> k;
        for(int j = 0; j < k; j++) {
            int boss;
            cin >> boss;
            adj[boss].push_back(ord);
        }
    }

    int best = INF;
    // root the tree at every possible vertex
    for(int boss = 1; boss <= n; boss++) {
        best = min(best, solve(boss));
    }

    cout << best;
    return 0;
}

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