제출 #1208446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208446		tgirolami09	Bosses (BOI16_bosses)	C++20	100 / 100	459 ms	724 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>

typedef long long ll;

using namespace std;

vector<int> children[5001];

struct person{
    int personId;
    int parentDepth;
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int nbPeople;
    cin >> nbPeople;

    for (int i = 0;i<nbPeople;++i){
        int nbBosses;
        cin >> nbBosses;
        for (int j = 0;j<nbBosses;++j){
            int boss;
            cin >> boss;
            children[boss].push_back(i+1);
        }
    }

    //Try everyone as a boss first
    ll bestSum = 1l<<60;
    for (int i = 1;i<=nbPeople;++i){
        // printf("\tNew try\n");
        ll currSum = 0;
        queue<person> toAdd;
        vector<bool> visited(nbPeople+1,false);
        visited[i] = true;
        int toBeVisited = nbPeople-1;
        toAdd.push({i,1});

        while(!(toAdd.empty())){
            person newPerson = toAdd.front();
            toAdd.pop();

            // printf("Added person %d for a cost of %d\n",newPerson.personId,newPerson.parentDepth);
            currSum+=newPerson.parentDepth;

            //Add all children if not seen
            for (int childId : children[newPerson.personId]){
                if (!visited[childId]){
                    visited[childId] = true;
                    --toBeVisited;
                    toAdd.push({childId,newPerson.parentDepth+1});
                }
            }
        }
        if (toBeVisited==0){
            bestSum = min(bestSum,currSum);
        }
    }
    cout << bestSum;
}

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