oj.uz

Submission #874595

# Submission time Handle Problem Language Result Execution time Memory
874595 2023-11-17T11:02:43 Z atom Bosses (BOI16_bosses) C++17
100 / 100
 930 ms 1048 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) {
        int sz = 0;
        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();
            ++sz;
            for (int v : gr[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    adj[u].push_back(v);
                    q.push(v);
                }
            }
        }

        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:72:9: note: in expansion of macro 'debug'
   72 |         debug(sz);
      |         ^~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 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 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 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 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 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 856 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 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 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 6 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 139 ms 896 KB Output is correct
15 Correct 38 ms 900 KB Output is correct
16 Correct 587 ms 984 KB Output is correct
17 Correct 930 ms 1048 KB Output is correct
18 Correct 924 ms 1048 KB Output is correct