Submission #704256

#	Time	Username	Problem	Language	Result	Execution time	Memory
704256		anha3k25cvp	Bosses (BOI16_bosses)	C++14	100 / 100	633 ms	668 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 1 + 1e5;
const int inf = 7 + 1e9;

int n;
vector <int> h;
vector <vector <int>> g;

int cal(int root) {
    h.assign(n + 1, 0);
    queue <int> q;
    q.push(root);
    h[root] = 1;
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt ++;
        for (int v : g[u])
            if (!h[v]) {
                h[v] = h[u] + 1;
                q.push(v);
            }
    }
    if (cnt < n)
        return inf;
    int ans = 0;
    for (int i = 1; i <= n; i ++)
        ans += h[i];
    return ans;
}

int main() {
#define TASKNAME "bosses"
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen( TASKNAME".inp", "r", stdin );
        freopen( TASKNAME".out", "w", stdout );
    }
    cin >> n;
    g.resize(n + 1);
    for (int i = 1; i <= n; i ++) {
        int k;
        cin >> k;
        while (k --) {
            int u;
            cin >> u;
            g[u].push_back(i);
        }
    }
    int ans = inf;
    for (int i = 1; i <= n; i ++)
        ans = min(ans, cal(i));
    cout << ans;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen( TASKNAME".inp", "r", stdin );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen( TASKNAME".out", "w", stdout );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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