Submission #704249

#	Time	Username	Problem	Language	Result	Execution time	Memory
704249		anha3k25cvp	Bosses (BOI16_bosses)	C++14	0 / 100	0 ms	212 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, a;
vector <vector <int>> g;

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

int main() {
#define TASKNAME ""
    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:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen( TASKNAME".inp", "r", stdin );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen( TASKNAME".out", "w", stdout );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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