Submission #522742

#	Time	Username	Problem	Language	Result	Execution time	Memory
522742		nikolapesic2802	Bosses (BOI16_bosses)	C++14	100 / 100	1196 ms	1192 KiB

bosses

#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=1LL;
    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=2000000000000000LL;
    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=0LL;
        bfs(root);
        racunaj(root);
      bool ok=1;
      for(int i=1;i<=n;i++)
        if(!pos[i])
          ok=0;
      if(ok)
        mini=min(mini, uk);
    }
    cout << mini;
    return 0;
}

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