oj.uz

Submission #884351

# Submission time Handle Problem Language Result Execution time Memory
884351 2023-12-07T08:25:37 Z vjudge1 Bosses (BOI16_bosses) C++17
100 / 100
 812 ms 1088 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pb push_back
#define pll array<ll, 2>
#define int long long

const int N = 5e3 + 4;
const ll INF = 1LL << 62;

int n;
bool vis[N];
vector<int> in[N], g[N];

pll dfs(int v) {
    pll ret = {0, 0};
    for (int u : g[v]) {
        pll res = dfs(u);
        ret[0] += res[0];
        ret[1] += res[1];
    }
    ++ret[0];
    ret[1] += ret[0];
    return ret;
}

ll bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;

    while (q.size() > 0) {
        int v = q.front();
        q.pop();
        for (int u : in[v]) {
            if (vis[u] == false) {
                vis[u] = true;
                g[v].pb(u);
                q.push(u);
            }
        }
    }
    return dfs(s)[1];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int v;
            cin >> v;
            --v;
            in[v].pb(i);
        }
    }

    ll ans = INF;
    for (int i = 0; i < n; ++i) {
        ll res = bfs(i);
        bool seeAll = true;
        for (int j = 0; j < n; ++j) {
            seeAll &= vis[j];
            g[j].clear();
            vis[j] = false;
        }
        if (seeAll == true) {
            ans = min(ans, res);
        }
    }
    cout << ans;

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 696 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 0 ms 700 KB Output is correct
10 Correct 1 ms 600 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 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 0 ms 696 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 0 ms 700 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 856 KB Output is correct
13 Correct 3 ms 856 KB Output is correct
14 Correct 205 ms 856 KB Output is correct
15 Correct 19 ms 856 KB Output is correct
16 Correct 807 ms 1088 KB Output is correct
17 Correct 808 ms 1064 KB Output is correct
18 Correct 812 ms 1056 KB Output is correct