Submission #1086763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086763		LOLOLO	Bosses (BOI16_bosses)	C++14	100 / 100	1058 ms	1116 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           s     second
#define           f     first
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    777*min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 5e3 + 1;
vector <int> lst[N], ed[N];
ll sum[N];
bool used[N];
int n;

ll cal(int u) {
    ll ans = 0, ss = 0;

    for (auto x : ed[u]) {
        ans += cal(x);
        ss += sum[x];
    }

    ss++;
    sum[u] = ss;
    return ans + sum[u];
}

ll build(int st) {
    for (int i = 1; i <= n; i++) {
        ed[i].clear();
        used[i] = 0;
        sum[i] = 0;
    }

    int cnt = 0;
    queue <int> dq;
    dq.push(st);
    used[st] = 1;

    while (sz(dq)) {
        int t = dq.front();
        dq.pop();
        cnt++;
        for (auto x : lst[t]) {
            if (used[x] == 0) {
                used[x] = 1;
                ed[t].pb(x);
                dq.push(x);
            }
        }
    }

    if (cnt == n) {
        return cal(st);
    }

    return 1e9;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int sz;
        cin >> sz;
        for (int j = 0; j < sz; j++) {
            int x;
            cin >> x;
            lst[x].pb(i);
        }
    }

    ll ans = 1e16;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, build(i));
    }

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

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