Submission #1303129

#TimeUsernameProblemLanguageResultExecution timeMemory
1303129SzymonKrzywdaBosses (BOI16_bosses)C++20
0 / 100
1 ms568 KiB
#include <iostream>
#include <vector>
#include <queue>


using namespace std;


const int MAXN = 5000 + 7;
vector<int> graf[MAXN];
vector<int> graf2[MAXN];
int odw[MAXN];
int ile = 0, suma2 = 0;

int dfs(int v) {
    int suma = 0;
    ile++;
    for (int s : graf2[v]) {
        suma += dfs(s);
    }
    suma2 += suma + 1;

    return suma + 1;
}


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

    int n, j, v;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> j;

        while (j--) {
            cin >> v;
            graf[v].push_back(i);
        }

    }

    int res = 1e9;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) graf2[j].clear();
        queue<int> kolejka;
        kolejka.push(i);
        odw[i] = i;
        while (!kolejka.empty()) {
            int v = kolejka.front();
            kolejka.pop();

            for (int s : graf[v]) {
                if (!odw[s]) {
                    graf2[v].push_back(s);
                    kolejka.push(s);
                    odw[s] = 1;
                }
            }
        }
        ile = 0;
        suma2 = 0;
        dfs(i);
        
        if (ile == n) {
           // cout << i << ' ' << suma2 << '\n';
            res = min(res, suma2);
        }
    }


    cout << res << '\n';


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...