Submission #994144

#	Time	Username	Problem	Language	Result	Execution time	Memory
994144		Sharky	Bosses (BOI16_bosses)	C++17	100 / 100	1079 ms	1100 KiB

bosses

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

const int N = 5001;
vector<int> adj[N], tree[N];
int sz[N], ans = 0, opt = 1e9, cnt = 0;
bool vis[N];

void dfs(int u) {
    sz[u] = 1;
    cnt++;
    for (auto& v : tree[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
    ans += sz[u];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1, j, x; i <= n; i++) {
        cin >> j;
        while (j--) {
            cin >> x;
            adj[x].push_back(i);
        }
    }
    for (int rt = 1; rt <= n; rt++) {
        ans = cnt = 0;
        for (int j = 1; j <= n; j++) {
            tree[j].clear();
            vis[j] = 0, sz[j] = 0;
        }
        queue<int> q;
        q.push(rt);
        vis[rt] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) if (!vis[v]) {
                q.push(v);
                tree[u].push_back(v);
                vis[v] = 1;
            }
        }
        dfs(rt);
        if (cnt == n) opt = min(opt, ans);
    }
    cout << opt << '\n';
}


//     1
//    2 3
//  456  78

//      8
//   4     3
// 1 1 1  1 1

// find sigma(sz[u])

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