oj.uz

Submission #985376

# Submission time Handle Problem Language Result Execution time Memory
985376 2024-05-17T17:08:00 Z Octa_pe_info Bosses (BOI16_bosses) C++17
0 / 100
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -