Submission #408822

#	Time	Username	Problem	Language	Result	Execution time	Memory
408822		danielcm585	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	460 KiB

bosses

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 5e3;
const ll INF = 1e15;
int n;
bool use[N+2];
ll val[N+2];
vector<int> lst[N+2], adj[N+2];

ll dfs(int cur, int par) {
    if (!use[cur]) return INF;
    ll ret = 0;
    val[cur] = 0;
    for (int nx : adj[cur]) {
        if (nx == par) continue;
        ret += dfs(nx,cur);
        val[cur] += val[nx];
    }
    val[cur]++;
    ret += val[cur];
    return ret;
}

ll bfs(int st) {
    for (int i = 1; i <= n; i++) adj[i].clear();
    memset(use,0,sizeof(use));
    queue<int> q;
    q.push(st); use[st] = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nx : lst[cur]) {
            if (use[nx]) continue;
            use[nx] = 1;
            adj[cur].push_back(nx);
            q.push(nx);
        }
    }
    // cout << st << " -> " << dfs(st,0) << '\n';
    // cout << ">> ";
    // for (int j = 1; j <= n; j++) cout << val[j] << ' ';
    // cout << '\n';
    return dfs(st,0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            lst[x].push_back(i);
        }
    }
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans,bfs(i));
    }
    cout << ans << '\n';
    return 0;
}

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