제출 #723599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723599		The_Samurai	Bosses (BOI16_bosses)	C++17	67 / 100	1550 ms	1224 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;

vector<int> cost;
vector<vector<int>> g;

void dfs(int u) {
    for (int v: g[u]) {
        dfs(v);
        cost[u] += cost[v];
    }
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> in(n + 1), out(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int j;
            cin >> j;
            in[j].emplace_back(i);
            out[i].emplace_back(j);
        }
    }
    int ans = 2e9;
    for (int i = 1; i <= n; i++) {
        // root -> i
        queue<pair<int, int>> qu;
        g.assign(n + 1, {});
        cost.assign(n + 1, 1);
        vector<bool> vis(n + 1);
        vis[i] = 1;
        for (int j: in[i]) {
            g[i].emplace_back(j);
            qu.push({j, i});
            vis[j] = 1;
        }
        while (!qu.empty()) {
            auto [u, p] = qu.front();
            qu.pop();
            for (int v: in[u]) {
                if (!vis[v]) {
                    g[u].emplace_back(v);
                    qu.push({v, u});
                    vis[v] = 1;
                }
            }
        }
        bool ok = 1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j]) ok = 0;
        }
        if (!ok) continue;
        dfs(i);
        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: 0 / 33