Submission #1209054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209054		badge881	Bosses (BOI16_bosses)	C++20	100 / 100	772 ms	1012 KiB

bosses

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

vector<vector<int>> baseListAdj, listAdj;

pair<int, int> dfs(int x)
{
    int ans = 0, sm = 1;
    for (auto v : listAdj[x])
    {
        auto [ansi, smi] = dfs(v);
        ans += ansi, sm += smi;
    }
    ans += sm;
    return {ans, sm};
}

signed main()
{
    int n;
    scanf("%d", &n);
    baseListAdj.resize(n), listAdj.resize(n);
    vector<int> cnt(n);
    for (int i = 0; i < n; i++)
    {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++)
        {
            int x;
            scanf("%d", &x);
            x--;
            baseListAdj[x].push_back(i);
        }
    }
    int ans = n * n;
    for (int t = 0; t < n; t++)
    {
        queue<int> q;
        q.push(t);
        vector<int> dist(n, 0);
        vector<bool> visited(n, 0);
        visited[t] = 1;
        for (auto &u : listAdj)
            u.clear();
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : baseListAdj[u])
                if (!visited[v])
                {
                    dist[v] = dist[u] + 1, visited[v] = 1;
                    q.push(v);
                    listAdj[u].push_back(v);
                }
        }
        bool ok = 1;
        for (int i = 0; i < n; i++)
            if (!visited[i])
                ok = 0;
        if (!ok)
            continue;
        ans = min(ans, dfs(t).first);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
bosses.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
bosses.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

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