제출 #1307761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307761		sharanpai	Bosses (BOI16_bosses)	C++20	100 / 100	858 ms	1440 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];
    }
}

vector<int> visited;
int version = 0;

bool makeTree(int start, const vector<vector<int>>& potentialChild, vector<vector<int>>& adjList) {
    queue<int> q;
    q.push(start);
    visited[start] = version;
    int rem = visited.size() - 1;

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

    if (rem > 0) 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;
    visited.assign(N, 0);
    vector<vector<int>> adjList(N);

    for (int root = 0; root < N; ++root) {
        if (potentialChild[root].empty()) continue;
        ++version;
        for (int i = 0; i < N; ++i) adjList[i].clear();

        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: 33 / 33