Submission #546746

#	Time	Username	Problem	Language	Result	Execution time	Memory
546746		Jomnoi	Bosses (BOI16_bosses)	C++17	100 / 100	743 ms	648 KiB

bosses

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

const int MAX_N = 5e3 + 10;
const long long INF = 1e18 + 7;

vector <int> adj[MAX_N];
bitset <MAX_N> visited;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while(k--) {
            int p;
            cin >> p;
            adj[p].push_back(i);
        }
    }

    long long ans = INF;
    for(int i = 1; i <= n; i++) {
        visited = 0;
        long long sum = 0;

        visited[i] = true;
        queue <pair <int, int>> q;
        q.emplace(i, 1);
        while(!q.empty()) {
            auto [u, c] = q.front();
            q.pop();

            sum += c;
            for(auto v : adj[u]) {
                if(visited[v] == false) {
                    visited[v] = true;
                    q.emplace(v, c + 1);
                }
            }
        }

        if(visited.count() == n) {
            ans = min(ans, sum);
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:46:28: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(visited.count() == n) {
      |            ~~~~~~~~~~~~~~~~^~~~

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