Submission #1217787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217787		CrabCNH	Bosses (BOI16_bosses)	C++20	100 / 100	461 ms	900 KiB

bosses

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 5e3 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

int n, k;
int a[maxN];
int visited[maxN];
int h[maxN];
vector <int> adj[maxN];
int s[maxN];

int bfs (int x) {
    for (int i = 1; i <= n; i ++) {
        h[i] = -1;
        s[i] = 1;
    }
    queue <int> q;
    q.push (x);
    stack <pii> st;
    h[x] = 0;
    while (!q.empty ()) {
        int u = q.front ();
        q.pop ();
        //cout << u << '\n';
        for (auto v : adj[u]) {
            if (h[v] != -1) {
                continue;
            }
            h[v] = h[u] + 1;
            st.push ({v, u});
            q.push (v);
        }
    }
    for (int i = 1; i <= n; i ++) {
        if (h[i] == -1) {
            return inf;
        }
    }
    int res = 0;
    //cout << st.size () << '\n';
    while (!st.empty ()) {
        auto [u, v] = st.top ();
        st.pop ();
        res += s[u];
        s[v] += s[u];
    } 
    res += s[x];
    //cout << res << '\n';
    return res;
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        for (int j = 1; j <= x; j ++) {
            int y;
            cin >> y;
            adj[y].push_back (i);
        }
    }
    int res = inf;
    for (int i = 1; i <= n; i ++) {
        minimize (res, bfs (i));
    }
    cout << res;
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

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

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