제출 #977082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977082		VMaksimoski008	Bosses (BOI16_bosses)	C++17	100 / 100	888 ms	1088 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5005;

int n, k, x, seen=0;
ll ans = 1e18, dp[maxn+5];
vector<int> graph[maxn+5], tree[maxn+5], vis(maxn+5);
queue<int> q;

ll dfs(int u) {
    dp[u] = 1;
    for(int &v : tree[u]) dp[u] += dfs(v);
    return dp[u];
}

int32_t main() {
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> k;
        for(int j=0; j<k; j++) {
            cin >> x;
            graph[x].push_back(i);
        } 
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) vis[j] = dp[j] = 0, tree[j].clear();
        q.push(i); vis[i] = 1; seen = 0;

        while(!q.empty()) {
            int u = q.front();
            q.pop();

            seen++;

            for(int &v : graph[u]) {
                if(vis[v]) continue;
                vis[v] = 1;
                tree[u].push_back(v);
                q.push(v);
            }
        }

        if(seen < n) continue;

        dfs(i);
        ll res = 0;
        for(int j=1; j<=n; j++) res += dp[j];
        ans = min(ans, res);
    }

    cout << ans << '\n';
    return 0;
}

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