제출 #680228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680228		Tigerpants	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	212 KiB

bosses

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;

const ll INF = 5000 * 10000;

vvll g;
ll n;

vb vis;
ll BFS(ll cur, ll height) {
    vll children;
    for (vll::iterator child = g[cur].begin(); child != g[cur].end(); child++) {
        if (!vis[*child]) {
            vis[*child] = true;
            children.push_back(*child);
        }
    }

    ll children_sum = 0;
    for (vll::iterator child = children.begin(); child != children.end(); child++) {
        children_sum += BFS(*child, height + 1);
    }

    return height + children_sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    g.resize(n);
    ll k_tmp;
    ll inp_tmp;
    for (int i = 0; i < n; i++) {
        cin >> k_tmp;
        for (int j = 0; j < k_tmp; j++) {
            cin >> inp_tmp;
            g[inp_tmp - 1].push_back(i);
        }
    }

    ll min_sum = INF;
    vis.resize(n);
    for (int i = 0; i < n; i++) {
        fill_n(vis.begin(), n, false);
        vis[i] = true;
        ll ans = BFS(i, 1);
        
        bool verify = true;
        for (int i = 0; i < n; i++) {verify &= vis[i];}

        if (verify) {min_sum = min<ll>(min_sum, ans);}
    }

    cout << min_sum << endl;

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33