oj.uz

Submission #860691

# Submission time Handle Problem Language Result Execution time Memory
860691 2023-10-13T19:04:45 Z Iliya_ Bosses (BOI16_bosses) C++17
100 / 100
 494 ms 852 KB 
//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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 576 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 576 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 576 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 576 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 572 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 576 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 576 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 572 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Correct 102 ms 716 KB Output is correct
15 Correct 17 ms 604 KB Output is correct
16 Correct 467 ms 824 KB Output is correct
17 Correct 481 ms 852 KB Output is correct
18 Correct 494 ms 604 KB Output is correct