oj.uz

답안 #390054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390054 2021-04-15T06:56:19 Z BThero Bosses (BOI16_bosses) C++17
100 / 100
 1424 ms 952 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = (int)5e3 + 5;
const int INF = (int)1e9;

vi g[MAXN], adj[MAXN];
int d[MAXN];
int n;

pair<ll, ll> dfs(int v) {
    pair<ll, ll> ret = mp(0, 0);

    for (int to : g[v]) {
        pair<ll, ll> cur = dfs(to);
        ret.fi += cur.fi;
        ret.se += cur.se;
    }

    ret.fi++;
    ret.se += ret.fi;
    return ret;
}

void solve() {
    cin >> n;

    rep (i, 1, n + 1) {
        int k;
        cin >> k;

        rep (j, 0, k) {
            int x;
            cin >> x;
            adj[x].pb(i);
        }
    }

    queue<int> q;
    ll ans = (ll)1e18;

    rep (i, 1, n + 1) {
        fill(d + 1, d + n + 1, INF);
        fill(g + 1, g + n + 1, vi());
        d[i] = 0;
        q.push(i);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int to : adj[v]) {
                if (d[to] == INF) {
                    d[to] = d[v] + 1;
                    g[v].pb(to);
                    q.push(to);
                }
            }
        }

        if (*max_element(d + 1, d + n + 1) != INF) {
            ans = min(ans, dfs(i).se);
        }
    } 

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;

    for (int i = 1; i <= tt; ++i) {
        solve();
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 210 ms 868 KB Output is correct
15 Correct 63 ms 716 KB Output is correct
16 Correct 726 ms 880 KB Output is correct
17 Correct 1402 ms 952 KB Output is correct
18 Correct 1424 ms 952 KB Output is correct