Submission #973128

#	Time	Username	Problem	Language	Result	Execution time	Memory
973128		canadavid1	Bosses (BOI16_bosses)	C++14	100 / 100	482 ms	788 KiB

bosses

#include <iostream>
#include <vector>

#include <algorithm>



int main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> coboss(N);
    for(int i = 0; i < N; i++)
    {
        int K;
        std::cin >> K;
        for(int j = 0; j < K; j++)
        {
            int l;
            std::cin >> l;
            coboss[l-1].push_back(i);
        }
    }
    int min = 1<<30;
    for(int head = 0; head < N; head++)
    {
        // bfs from head
        std::vector<int> curr = {head};
        std::vector<bool> seen(N); seen[head] = 1;
        std::vector<int> next;
        int c = 0;
        for(int d = 1;curr.size();d++)
        {
            for(auto n: curr)
            {
                c += d;
                for(auto ne : coboss[n])
                {
                    if(!seen[ne]) {next.push_back(ne); seen[ne] = 1;}
                }
            }
            curr = std::move(next);
            next.clear();
        }
        if (c < min && std::all_of(seen.begin(),seen.end(),[](auto x){return x;})) min = c;
    }
    std::cout << min << "\n";
}

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