Submission #723605

#	Time	Username	Problem	Language	Result	Execution time	Memory
723605		The_Samurai	Bosses (BOI16_bosses)	C++17	100 / 100	636 ms	828 KiB

bosses

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;


void solve() {
    int n;
    cin >> n;
    vector<vector<int>> in(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int j;
            cin >> j;
            in[j].emplace_back(i);
        }
    }
    int ans = 2e9;
    vector<pair<int, int>> queue(n + 1);
    for (int i = 1; i <= n; i++) {
        // root -> i
        queue[0] = {i, 0};
        vector<bool> vis(n + 1);
        vector<int> cost(n + 1, 1);
        int pos = 1;
        vis[i] = 1;
        for (int j = 0; j < pos; j++) {
            int u = queue[j].first;
            for (int v: in[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    queue[pos] = {v, u};
                    pos++;
                }
            }
        }
        if (pos != n) continue;
        for (int j = n - 1; j >= 0; j--) {
            cost[queue[j].second] += cost[queue[j].first];
        }
        int now = 0;
        for (int j = 1; j <= n; j++)
            now += cost[j];
        ans = min(ans, now);
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

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