oj.uz

Submission #994144

# Submission time Handle Problem Language Result Execution time Memory
994144 2024-06-07T07:30:23 Z Sharky Bosses (BOI16_bosses) C++17
100 / 100
 1079 ms 1100 KB 
#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.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 700 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 181 ms 1024 KB Output is correct
15 Correct 22 ms 860 KB Output is correct
16 Correct 796 ms 1032 KB Output is correct
17 Correct 1079 ms 860 KB Output is correct
18 Correct 1070 ms 1100 KB Output is correct