Submission #322564

#	Time	Username	Problem	Language	Result	Execution time	Memory
322564		Habitus	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	620 KiB

bosses

#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;
}

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