oj.uz

Submission #860069

# Submission time Handle Problem Language Result Execution time Memory
860069 2023-10-11T13:57:54 Z kh0i Bosses (BOI16_bosses) C++17
100 / 100
 394 ms 856 KB 
#include "bits/stdc++.h"
using namespace std;

#define F first
#define S second
#define sz(x) (int)((x).size())
using ll = long long; 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 5003;

int n, ans = INT_MAX, d[N];
vector<int> g[N];

void bfs(int st){
    memset(d, -1, sizeof(d));
    d[st] = 1;
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : g[u]){
            if(d[v] == -1){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    int tot = 0;
    for(int i = 1; i <= n; ++i){
        if(d[i] == -1)
            return;
        tot += d[i];
    }
    ans = min(ans, tot);
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int k, u;
        cin >> k;
        for(int j = 1; j <= k; ++j){
            cin >> u;
            g[u].push_back(i);
        }
    }
    for(int i = 1; i <= n; ++i){
        bfs(i);
    }
    cout << ans;
}


int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 584 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 70 ms 856 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 394 ms 776 KB Output is correct
17 Correct 370 ms 792 KB Output is correct
18 Correct 389 ms 792 KB Output is correct