Submission #50879

#	Time	Username	Problem	Language	Result	Execution time	Memory
50879		luciocf	Bosses (BOI16_bosses)	C++14	100 / 100	1321 ms	1236 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e3+10;

int n, pai[MAXN], nivel[MAXN], ans[MAXN];
bool mark[MAXN];
vector<int> grafo[MAXN];

int BFS(int u)
{
    memset(mark, 0, sizeof mark);
    memset(ans, 0, sizeof ans);
    queue<int> fila;
    vector<int> level[MAXN];
    fila.push(u), mark[u] = 1, nivel[u] = 0;
    int qtd = 1, maxniv = 0, k = 0;

    while (!fila.empty())
    {
        int x = fila.front();
        fila.pop();
        for (int i = 0; i < grafo[x].size(); i++)
        {
            int v = grafo[x][i];
            if (mark[v]) continue;

            pai[v] = x, nivel[v] = nivel[x]+1;
            level[nivel[v]].push_back(v);
            maxniv = max(maxniv, nivel[v]);

            mark[v] = 1, fila.push(v);
            qtd++;
        }
    }
    if (qtd < n) return 1000000000;

    for (int i = maxniv; i > 0; i--)
    {
        for (int j = 0; j < level[i].size(); j++)
        {
            int v = level[i][j];
            ans[v]++;
            ans[pai[v]] += ans[v];
            k += ans[v];
        }
    }
    k += ans[u]+1;
    return k;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int m;
        cin >> m;
        while (m--)
        {
            int u;
            cin >> u;
            grafo[u].push_back(i);
        }
    }
    int out = 1e9;
    for (int i = 1; i <= n; i++)
        out = min(out, BFS(i));
    cout << out << "\n";
}

Compilation message (stderr)

bosses.cpp: In function 'int BFS(int)':
bosses.cpp:24:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < grafo[x].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~
bosses.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < level[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~~~

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