Submission #1310256

#TimeUsernameProblemLanguageResultExecution timeMemory
1310256nekolieBosses (BOI16_bosses)C++20
0 / 100
1 ms572 KiB
// So that's how you want it, womanizer?!
// That's rude. It's pure love.
// Then I fight for justice!
#include <bits/stdc++.h>
using namespace std;

int n; vector<int> g[5001];
long long solve(int v0) {
    vector<int> vivi; queue<int> q;
    int rozm[n+1], p[n+1]; bool odw[n+1];
    for (int i = 1; i <= n; i++)
        rozm[i] = 1, odw[i] = false;
    p[v0] = 0, q.push(v0), odw[v0] = true;
    while (!q.empty()) {
        int v = q.front(); q.pop(), vivi.push_back(v);
        for (int u : g[v])
            if (!odw[u])
                p[u] = v, odw[u] = true, q.push(u);
    }
    long long suma = 0;
    while (!vivi.empty())
        suma += rozm[vivi.back()], rozm[p[vivi.back()]] += rozm[vivi.back()], vivi.pop_back();
    return suma;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n; int m,x;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 0; j < m; j++)
            cin >> x, g[x].push_back(i);
    }
    long long odp = (1ll<<61);
    for (int i = 1; i <= n; i++)
        odp = min(odp,solve(i));
    cout << odp << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...