Submission #408825

#TimeUsernameProblemLanguageResultExecution timeMemory
408825danielcm585Bosses (BOI16_bosses)C++14
67 / 100
1544 ms908 KiB
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 5e3;
const int INF = 1e9;
int n;
bool use[N+2];
int val[N+2];
vector<int> lst[N+2], adj[N+2];

int dfs(int cur, int par) {
    int ret = 0;
    val[cur] = 0;
    for (int nx : adj[cur]) {
        if (nx == par) continue;
        ret += dfs(nx,cur);
        val[cur] += val[nx];
    }
    val[cur]++;
    ret += val[cur];
    return ret;
}

int bfs(int st) {
    for (int i = 1; i <= n; i++) {
        use[i] = 0;
        adj[i].clear();
    }
    queue<int> q;
    q.push(st); use[st] = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nx : lst[cur]) {
            if (use[nx]) continue;
            use[nx] = 1;
            adj[cur].push_back(nx);
            q.push(nx);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!use[i]) return INF;
    }
    return dfs(st,0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            lst[x].push_back(i);
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans,bfs(i));
    }
    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...