Submission #30721

#	Time	Username	Problem	Language	Result	Execution time	Memory
30721		RayaBurong25_1	Bosses (BOI16_bosses)	C++14	100 / 100	723 ms	2224 KiB

bosses

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 1000000000
std::vector<int> AdjList[5005];
int min(int a, int b)
{
    return (a < b)?a:b;
}
int Vis[5005];
int cnt, sz;
int sum;
std::queue<int> Q;
int H[5005];
int N;
void BFS(int u)
{
    // printf("DFS %d %d\n", u, pa);
    int i;
    for (i = 1; i <= N; i++)
        H[i] = INF;
    Q.push(u);
    H[u] = 1;
    sum += H[u];
    sz++;
    int p;
    int v, s;
    while (!Q.empty())
    {
        p = Q.front();
        Q.pop();
        s = AdjList[p].size();
        for (i = 0; i < s; i++)
        {
            v = AdjList[p][i];
            if (H[v] == INF)
            {
                Q.push(v);
                H[v] = H[p] + 1;
                sum += H[v];
                sz++;
            }
        }
    }
}
int main()
{
    scanf("%d", &N);
    int i, j, K;
    int p;
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &K);
        for (j = 0; j < K; j++)
        {
            scanf("%d", &p);
            AdjList[p].push_back(i);
        }
    }
    int Ans = INF;
    // int r;
    for (i = 1; i <= N; i++)
    {
        // printf("Root %d\n", i);
        cnt++;
        sz = 0;
        sum = 0;
        BFS(i);
        // printf("%lld\n", sum);
        if (sz == N)
            Ans = min(Ans, sum);
    }
    printf("%d", Ans);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
bosses.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &K);
                        ^
bosses.cpp:56:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &p);
                            ^

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