Submission #985347

#	Time	Username	Problem	Language	Result	Execution time	Memory
985347		ionut2212	Bosses (BOI16_bosses)	C++17	100 / 100	449 ms	856 KiB

bosses

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

using namespace std;
vector<vector<int > > v;
int viz[10011];
/*int suma(int poz)
{
    if(sum[poz] == 0)
    {
        if(nivel[poz].size() == 0)
            return 1;
        else
            return 1 +
    }
}*/
int main()
{
    int n;
    cin >> n;
    v.resize(n+1);
    for(int i = 1; i<=n; i++)
    {
        int x;
        cin >> x;
        for(int j = 1; j<=x; j++)
        {
            int y;
            cin >> y;
            v[y].push_back(i);
        }
    }
    int sum, minim = 1e9 + 1e9;
    for(int j = 1; j<=n; j++)
    {
        queue<int> q;
        q.push(j);
        viz[j] = 1;
        sum = 1;
        int s = 0;
        while(!q.empty())
        {
            int nod = q.front();
            for(int i = 0; i < v[nod].size(); i++)
            {
                int vecin = v[nod][i];
                if(!viz[vecin])
                {
                    s++;
                    viz[vecin] = viz[nod] + 1;
                    sum+=viz[vecin];
                    q.push(vecin);
                }
            }
            //cout << nod << ' ';
            q.pop();
        }
        //cout <<' '<< sum << '\n';
        if(s == n-1)
            minim = min(minim, sum);
        for(int i = 1; i <= n; i++) viz[i] = 0;
    }
    cout << minim;
    return 0;
}
/// smin => noduri cu cat mai multe elemente

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int i = 0; i < v[nod].size(); i++)
      |                            ~~^~~~~~~~~~~~~~~

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