Submission #50878

#	Time	Username	Problem	Language	Result	Execution time	Memory
50878		luciocf	Bosses (BOI16_bosses)	C++14	67 / 100	1575 ms	1160 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e3+10;

int n, size[MAXN], k;
bool mark[MAXN];
vector<int> grafo[MAXN], aux[MAXN];

bool BFS(int u)
{
    memset(mark, 0, sizeof mark);
    queue<int> fila;
    fila.push(u), mark[u] = 1;
    int qtd = 1;

    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;
            aux[x].push_back(v);
            mark[v] = 1, fila.push(v);
            qtd++;
        }
    }
    if (qtd < n) return false;
    return true;
}

int DFS(int u, int p)
{
    for (int i = 0; i < aux[u].size(); i++)
    {
        int v = aux[u][i];
        if (v == p) continue;
        size[u] += DFS(v, u);
    }
    size[u]++;
    k += size[u];
    return size[u];
}

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 ans = 1e9;
    for (int i = 1; i <= n; i++)
    {
        memset(size, 0, sizeof size);
        for (int j = 1; j <= n; j++) aux[j].clear();
        bool ok = BFS(i);
        if (!ok) continue;

        k = 0;
        DFS(i, -1);
        ans = min(ans, k);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

bosses.cpp: In function 'bool BFS(int)':
bosses.cpp:22:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < grafo[x].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~
bosses.cpp: In function 'int DFS(int, int)':
bosses.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < aux[u].size(); i++)
                     ~~^~~~~~~~~~~~~~~

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