제출 #329582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
329582		gustason	Bosses (BOI16_bosses)	C++14	22 / 100	1 ms	492 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 biggest_dep_1 = 0;

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);

    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;
                }
            }
        }
        if (d == 1) {
            if ((int) dep[2].size() < biggest_dep_1) return INF;
            biggest_dep_1 = (int) dep[2].size();
        }
    }

    if (count(conn.begin(), conn.end(), true) != 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: 0 / 45
• Subtask 3: 0 / 33