제출 #1307759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307759		sharanpai	Bosses (BOI16_bosses)	C++20	67 / 100	1593 ms	1428 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void DFS(int cur, int parent, const vector<vector<int>>& adjList, vector<long long>& salary) {
    salary[cur] = 1;
    for (int nxt : adjList[cur]) {
        if (nxt == parent) continue;
        DFS(nxt, cur, adjList, salary);
        salary[cur] += salary[nxt];
    }
}

bool makeTree(int start, const vector<vector<int>>& potentialChild, vector<vector<int>>& adjList) {
    queue<int> q;
    vector<bool> visited(adjList.size());   // adjList.size() == N
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nxt : potentialChild[cur]) {
            if (!visited[nxt]) {
                adjList[cur].push_back(nxt);
                adjList[nxt].push_back(cur);
                q.push(nxt);
                visited[nxt] = true;
            }
        }
    }

    for (bool b : visited)
        if (!b) return false;
    return true;
}

int main()
{
    int N; cin >> N;
    vector<vector<int>> preferences(N), potentialChild(N);
    for (int i = 0, ki; i < N; ++i) {
        cin >> ki;
        preferences[i].resize(ki);
        for (int j = 0; j < ki; ++j) {
            cin >> preferences[i][j];
            --preferences[i][j];
            potentialChild[preferences[i][j]].push_back(i);
        }
    }

    long long minTotal = -1;
    for (int root = 0; root < N; ++root) {
        if (potentialChild[root].empty()) continue;
        vector<vector<int>> adjList(N);
        if (!makeTree(root, potentialChild, adjList)) continue;

        vector<long long> salary(N, 0);
        DFS(root, -1, adjList, salary);

        long long total = 0;
        for (long long s : salary) total += s;
        if (minTotal == -1 || total < minTotal) minTotal = total;
    }
    cout << minTotal;
}

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