oj.uz

Submission #489329

# Submission time Handle Problem Language Result Execution time Memory
489329 2021-11-22T13:06:11 Z jalsol Bosses (BOI16_bosses) C++17
100 / 100
 640 ms 680 KB 
// looking to shine brighter in this world...

#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

using namespace std;

const bool __initialization = [] {
    cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "empty"
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 5000 + 5;

int n;
vector<int> g[maxn];

queue<int> q;
ll ans = linf;
ll d[maxn];
 
void Bfs(int src) {
    memset(d, 0x3f, sizeof(d));
    d[src] = 0;
    q.push(src);

    while (isz(q)) {
        int u = q.front(); q.pop();

        Fe (v : g[u]) {
            if (d[v] >= linf) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    ll sum = 0;

    For (i, 1, n) {
        sum += d[i];
        if (d[i] >= linf) break;
    }

    chmin(ans, sum);
}

signed main() {
    cin >> n;

    For (i, 1, n) {
        int ne; cin >> ne;
        Rep (_, ne) {
            int x; cin >> x;
            g[x].push_back(i);
        }
    }

    For (i, 1, n) Bfs(i);

    ans += n;
    cout << ans << '\n';
}
// https://oj.uz/problem/view/BOI16_bosses

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 3 ms 508 KB Output is correct
14 Correct 113 ms 580 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 485 ms 656 KB Output is correct
17 Correct 640 ms 672 KB Output is correct
18 Correct 633 ms 680 KB Output is correct