oj.uz

Submission #874592

# Submission time Handle Problem Language Result Execution time Memory
874592 2023-11-17T10:59:03 Z atom Bosses (BOI16_bosses) C++17
100 / 100
 911 ms 1144 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#define fi first
#define se second
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

using pii = pair < int, int >;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int N = 5e3 + 5;

int n;
int dp[N], f[N];
vector <int> adj[N], gr[N];

void dfs(int u, int p) {
    int sum = 0;
    for (int v : adj[u]) {
        if (v ^ p) {
            dfs(v, u);
            sum += dp[v];
            f[u] += f[v];
        }
    }
    dp[u] = sum + 1;
    f[u] += dp[u];
}

void run_case() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int k; cin >> k;
        for (int j = 1; j <= k; ++j) {
            int x; cin >> x;
            gr[x].push_back(i);
        }
    }


    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        for (int x = 1; x <= n; ++x) {
            dp[x] = f[x] = 0;
            adj[x].clear();
        }

        // BFS for optimal tree 
        queue <int> q;
        vector <bool> vis(n + 5, 0);
        q.push(i);
        vis[i] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : gr[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    adj[u].push_back(v);
                    q.push(v);
                }
            }
        }

        int sz = (int) accumulate(vis.begin(), vis.end(), 0);
        debug(sz);
        if (sz == n) {
            dfs(i, 0);
            ans = min(ans, f[i]);
        }
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int Test = 1;
    //cin >> Test;
    for (int test = 1; test <= Test; test++){

        run_case();
    }
}

Compilation message

bosses.cpp: In function 'void run_case()':
bosses.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 166
      |                    ^~~
bosses.cpp:71:9: note: in expansion of macro 'debug'
   71 |         debug(sz);
      |         ^~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 604 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 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 604 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 4 ms 860 KB Output is correct
14 Correct 173 ms 1144 KB Output is correct
15 Correct 45 ms 808 KB Output is correct
16 Correct 540 ms 1044 KB Output is correct
17 Correct 897 ms 1116 KB Output is correct
18 Correct 911 ms 1116 KB Output is correct