제출 #860691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860691		Iliya_	Bosses (BOI16_bosses)	C++17	100 / 100	494 ms	852 KiB

bosses

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef long long ll; 

const ll N = 5e3+7; 
vector<ll> g[N];
ll dist[N];
queue<ll> q; 

ll bfs(ll v, ll n){
    for(ll i=1; i<=n; i++) dist[i] = 1e12; 
    dist[v] = 1; 
    q.push(v); 
    while(q.size()){
        ll u = q.front();
        q.pop();
        for(ll w : g[u]){
            if (dist[w] == 1e12){
                dist[w] = dist[u] + 1; 
                q.push(w); 
            }
        }
    }
    ll tmp = 0; 
    for(ll i=1; i<=n; i++) tmp += dist[i]; 
    return tmp;
}  

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    ll n; cin >> n; 
    for(ll i=1; i<=n; i++){
        ll k; cin >> k;
        for(ll j=1; j<=k; j++){
            ll v; cin >> v; 
            g[v].push_back(i); 
        }
    }
    ll ans = 1e12;
    for(ll i=1; i<=n; i++) ans = min(ans,bfs(i,n)); 
    cout << ans << endl;

	return 0;
}

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