Submission #717677

#TimeUsernameProblemLanguageResultExecution timeMemory
717677vjudge1Bosses (BOI16_bosses)C++17
100 / 100
1496 ms960 KiB
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[5010];
vector<int> g[5010];
vector<bool> vis(5010, false);
vector<int> cnt(5010, 0);
int n, res, check;

void dfs(int u) {
    check++;
    for(auto v : g[u]) {
        dfs(v);
        cnt[u] += cnt[v];
    }
    cnt[u]++;
    return;
}

void solve(int s) {
    for(int i = 1; i <= n; i++) {
        g[i].clear(); vis[i] = false; cnt[i] = 0;
    }
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto v : adj[u]) {
            if(vis[v] == false) {
                q.push(v);
                vis[v] = true;
                g[u].push_back(v);
            }
        }
    }
    check = 0;
    dfs(s);
    if(check != n) {
        return;
    }
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += cnt[i];
    }
    res = min(res, sum);
    return;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        while(k--) {
            int v; cin >> v;
            adj[v].push_back(i);
        }
    }
    res = INT_MAX;
    for(int i = 1; i <= n; i++) {
        solve(i);
    }
    cout << res << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...