제출 #322565

#제출 시각아이디문제언어결과실행 시간메모리
322565HabitusBosses (BOI16_bosses)C++14
0 / 100
1 ms620 KiB
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, mini;
vector<ll> graf[5010], detsa[5010];
bool pos[5010];
ll uk;
void bfs(ll poc) {
    queue<ll> q;
    pos[poc]=true;
    q.emplace(poc);
    while(!q.empty()) {
        ll 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);
        }
    }
}
ll racunaj(ll node) {
    ll 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(ll i=1; i<=n; ++i) {
        ll k; cin >> k;
        while(k--) {
            ll x; cin >> x;
            graf[x].push_back(i);
        }
    }
    for(ll root=1; root<=n; ++root) {
        for(ll i=1; i<=n; ++i) pos[i]=false;
        for(ll 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...