제출 #985376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
985376		Octa_pe_info	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	348 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
#include <climits>   // For INT_MAX
#include <algorithm> // For std::count

using namespace std;

vector<vector<int>> adj;
vector<bool> visited;
vector<int> level;

void bfs(int root, int n) {
    queue<int> q;
    visited.assign(n + 1, false);  // Reset visited for each BFS
    level.assign(n + 1, 0);        // Reset level for each BFS

    visited[root] = true;
    q.push(root);
    level[root] = 0;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int neighbor : adj[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                level[neighbor] = level[current] + 1;
                q.push(neighbor);
            }
        }
    }
}

int calculateSalaries(int node) {
    int salary = 1;
    for (int child : adj[node]) {
        if (level[child] == level[node] + 1) {
            salary += calculateSalaries(child);
        }
    }
    return salary;
}

int main() {
    int n;
    cin >> n;

    adj.resize(n + 1);
    visited.resize(n + 1);
    level.resize(n + 1);

    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            adj[x].push_back(i);
        }
    }

    int minimalTotalSalary = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        bfs(i, n);

        if (std::count(visited.begin() + 1, visited.end(), true) == n) {  // Check if all nodes are visited
            int totalSalary = 0;
            for (int j = 1; j <= n; ++j) {
                if (level[j] == 0) {  // Start DFS only from roots
                    totalSalary += calculateSalaries(j);
                }
            }
            minimalTotalSalary = min(minimalTotalSalary, totalSalary);
        }
    }

    cout << minimalTotalSalary;
    return 0;
}

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