Submission #1310257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310257		nekolie	Bosses (BOI16_bosses)	C++20	0 / 100	1 ms	572 KiB

bosses

// 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())
        rozm[p[vivi.back()]] += rozm[vivi.back()], vivi.pop_back();
    for (int i = 1; i <= n; i++)
        suma += rozm[i];
    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;
}

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