oj.uz

Submission #483043

# Submission time Handle Problem Language Result Execution time Memory
483043 2021-10-27T14:42:06 Z jalsol Bosses (BOI16_bosses) C++17
100 / 100
 1243 ms 716 KB 
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#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 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;
int pre[maxn];

void Bfs(int src) {
    memset(pre + 1, 0, sizeof(int) * n);
    q.push(src);
    pre[src] = -1;

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

        Fe (v : g[u]) {
            if (!pre[v]) {
                pre[v] = u;
                q.push(v);
            }
        }
    }
}

int sz[maxn];

void Dfs(int u) {
    sz[u] = 1;

    Fe (v : g[u]) {
        if (pre[v] == u) {
            Dfs(v);
            sz[u] += sz[v];
        }
    }
}

signed main() {
    cin >> n;

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

    ll ans = inf;

    For (i, 1, n) {
        Bfs(i);
        memset(sz + 1, 0, sizeof(int) * n);
        Dfs(i);

        if (count(pre + 1, pre + n + 1, 0)) continue;

        ll sum = accumulate(sz + 1, sz + n + 1, 0LL);
        chmin(ans, sum);
    }

    cout << ans << '\n';
}

// this can't be right...

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 5 ms 508 KB Output is correct
14 Correct 242 ms 716 KB Output is correct
15 Correct 18 ms 576 KB Output is correct
16 Correct 970 ms 708 KB Output is correct
17 Correct 1233 ms 712 KB Output is correct
18 Correct 1243 ms 676 KB Output is correct