Submission #1279784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279784		SSKMF	Bosses (BOI16_bosses)	C++20	100 / 100	395 ms	748 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

vector <int> adiacenta[5001];
int distanta[5001] , moment[5001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri;
    cin >> numar_noduri;

    for (int nod = 1 ; nod <= numar_noduri ; nod++)
    {
        int grad;
        cin >> grad;

        while (grad--)
        {
            int sursa; cin >> sursa;
            adiacenta[sursa].push_back(nod);
        }
    }

    int minim = INT32_MAX;
    for (int radacina = 1 ; radacina <= numar_noduri ; radacina++)
    {
        distanta[radacina] = 1;
        moment[radacina] = radacina;

        int suma = 1 , vizitat = 1;
        queue <int> candidati; candidati.push(radacina);
        while (!candidati.empty())
        {
            const int nod = candidati.front();
            candidati.pop();

            for (auto& vecin : adiacenta[nod]) {
                if (moment[vecin] != radacina)
                {
                    moment[vecin] = radacina;
                    distanta[vecin] = distanta[nod] + 1;
                    suma += distanta[vecin];
                    candidati.push(vecin);
                    vizitat++;
                }
            }
        }

        if (vizitat == numar_noduri)
            { minim = min(minim , suma); }
    }

    cout << minim;
    return 0;
}

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