Submission #1185592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185592		GoBananas69	Bosses (BOI16_bosses)	C++20	22 / 100	1 ms	328 KiB

bosses

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const long long MOD = 1000000007;
const int maxn = 505;
const int Lg = 23;
const long long inf = 1000000000;

typedef long long ll;

vector<ll> g[maxn], c[maxn];
bool use[maxn];
ll cu = 0;

ll dfs(int v, int p = -1) {
    ll x = 0;
    for (int to : c[v]) {
        if (to == p)
            continue;
        x += dfs(to, v);
    }
    cu += x + 1;
    return x + 1;
}

void solve() {
    int n;
    cin >> n;
    pair<ll, ll> mb = {-inf, -inf};
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int p;
            cin >> p;
            g[p].push_back(i);
            mb = max(mb, make_pair((ll)g[p].size(), (ll)p));
        }
    }

    ll ans = inf;
    for (int i = 1; i <= n; i++) {
        if (g[i].empty())
            continue;
        if (abs((int)g[i].size() - (int)mb.first) > 1)
            continue;
        for (int j = 1; j <= n; j++)
            c[j].clear();

        queue<int> q;
        q.push(i);
        memset(use, 0, sizeof(use));
        use[i] = true;
        int h = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto to : g[v]) {
                if (use[to])
                    continue;
                c[v].push_back(to);
                q.push(to);
                use[to] = true;
                h++;
            }
        }
        if (h == n) {
            cu = 0;
            dfs(i);
            ans = min(ans, cu);
        }
    }
    cout << ans << "\n";
}

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

    int tt = 1;
    while (tt--) {
        solve();
    }
    return 0;
}

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