Submission #1346344

#TimeUsernameProblemLanguageResultExecution timeMemory
1346344tamir1Bosses (BOI16_bosses)C++20
100 / 100
400 ms196540 KiB
#include <bits/stdc++.h>
using namespace std;


#define int long long
#define ff first
#define ss second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back


vector<vector<int>> adj;
int n;

void bfs(int node, vector<int> &dist) {
    dist.assign(n, -1);
    queue<int> q;
    q.push(node);
    dist[node] = 0;
    while(!q.empty()) {
        int node = q.front(); q.pop();


        for(int v : adj[node]) {
            if(dist[v] == -1) {
                dist[v] = dist[node] + 1;
                q.push(v);
            }
        }
    }
}


signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    adj.assign(n, {});
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        while(k--) {
            int u;
            cin >> u;
            u--;
            adj[u].pb(i);
        }
    }
    vector<vector<int>> dist(n);
    int ans = 1e18;
    for(int i = 0; i < n; i++) {
        bfs(i, dist[i]);
        bool unen = 1;
        int sum = n;
        for(int j = 0; j < n; j++) {
            if(dist[i][j] == -1) {
                unen = 0;
                break;
            }
            sum += dist[i][j];
        }
        if(!unen) continue;
        ans = min(ans, sum);
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...