Submission #1307756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307756		sharanpai	Bosses (BOI16_bosses)	C++20	0 / 100	1 ms	568 KiB

bosses

#include <iostream>
#include <vector>
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];
    }
}

void makeTree(int cur, const vector<vector<int>>& potentialChild, vector<int>& depth, vector<int>& parent) {
    for (int child : potentialChild[cur]) {
        if (parent[child] == child) continue;
        if (depth[child] == -1 || depth[child] > depth[cur] + 1) {
            depth[child] = depth[cur] + 1;
            parent[child] = cur;
            makeTree(child, potentialChild, depth, parent);
        }
    }
}

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<int> depth(N, -1), parent(N, -1);
        depth[root] = 0; 
        makeTree(root, potentialChild, depth, parent);
        vector<vector<int>> adjList(N);
        bool valid = true;
        for (int j = 0; j < N; ++j) {
            if (j == root) continue;
            if (parent[j] == -1) {
                valid = false; break;
            }
            adjList[j].push_back(parent[j]);
            adjList[parent[j]].push_back(j);
        }
        if (!valid) continue;

        vector<long long> salary(N, 0);
        DFS(0, -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: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33