제출 #1324038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324038		sh_qaxxorov_571	Bosses (BOI16_bosses)	C++20	100 / 100	365 ms	716 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

/**
 * Har bir xodimni ildiz sifatida tekshirib chiqamiz.
 * Jami ish haqi yig'indisi har bir tugunning chuqurlik darajalari yig'indisiga teng.
 */

const long long INF = 1e18;
vector<int> adj[5005]; // Boss bo'lishi mumkin bo'lganlar ro'yxati (teskari graf)

long long solve(int root, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[root] = 1; // Ildizning ish haqi darajasi 1 dan boshlanadi
    q.push(root);

    long long total_salary = 0;
    int visited_count = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        visited_count++;
        total_salary += dist[u];

        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    // Agar barcha xodimlar iyerarxiyaga kirmagan bo'lsa, bu ildiz yaroqsiz
    if (visited_count != n) return INF;
    return total_salary;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int boss;
            cin >> boss;
            // Xodim i bossni qabul qiladi, demak bossdan i ga yo'l bor
            adj[boss].push_back(i);
        }
    }

    long long min_total_salary = INF;

    // Har bir xodimni potensial "Bosh Boss" (ildiz) sifatida ko'rib chiqamiz
    for (int i = 1; i <= n; i++) {
        min_total_salary = min(min_total_salary, solve(i, n));
    }

    cout << min_total_salary << endl;

    return 0;
}

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