Submission #322564

#TimeUsernameProblemLanguageResultExecution timeMemory
322564HabitusBosses (BOI16_bosses)C++14
0 / 100
1 ms620 KiB
#include<bits/stdc++.h>
using namespace std;

int n, mini;
vector<int> graf[5010], detsa[5010];
bool pos[5010];
int uk;
void bfs(int poc) {
    queue<int> q;
    pos[poc]=true;
    q.emplace(poc);
    while(!q.empty()) {
        int tren=q.front(); q.pop();
        for(auto adj:graf[tren]) {
            if(pos[adj]) continue;
            pos[adj]=true;
            q.emplace(adj);
            detsa[tren].push_back(adj);
        }
    }
}
int racunaj(int node) {
    int suma=1;
    for(auto dete:detsa[node]) {
        suma+=racunaj(dete);
    }
    uk+=suma;
    return suma;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    mini=2000000000;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        int k; cin >> k;
        while(k--) {
            int x; cin >> x;
            graf[x].push_back(i);
        }
    }
    for(int root=1; root<=n; ++root) {
        for(int i=1; i<=n; ++i) pos[i]=false;
        for(int i=1; i<=n; ++i) detsa[i].clear();

        uk=0;
        bfs(root);
        racunaj(root);
        mini=min(mini, uk);
    }
    cout << mini;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...