Submission #596580

#	Time	Username	Problem	Language	Result	Execution time	Memory
596580		1zaid1	Bosses (BOI16_bosses)	C++17	100 / 100	1194 ms	1228 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long

const int M = 1e4+2;
vector<int> node[M], nod[M];
bitset<5005> vis;
int n;

pair<int, int> dfs(int s) {
    int a = 0, b = 0;
    vis[s] = true;
    for (int i:nod[s]) {
        if (!vis[i]) {
            auto [x, y] = dfs(i);
            a += x; b += y;
        }
    } return {a+1, b+a+1};
}

int solve(int s) {
    vis = 0;
    vis[s] = true;
    queue<int> q;
    q.push(s);
    int cnt = 0;
    for (int i = 1; i <= n; i++) nod[i].clear();
    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (int i:node[f]) {
            if (!vis[i]) {
                vis[i] = true;
                nod[f].push_back(i);
                q.push(i);
            }
        } cnt++;
    } vis = 0;
    if (cnt != n) return INT_MAX;
    return dfs(s).second;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;

        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            node[a].push_back(i);
        }
    }

    int mn = INT_MAX;
    for (int i = 1; i <= n; i++) {
        mn = min(mn, solve(i));
    } cout << mn << endl;

    return 0;
}
/*
4
1 4
3 1 3 4
2 1 2
1 3

*/

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