제출 #713630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713630		_martynas	Bosses (BOI16_bosses)	C++11	100 / 100	653 ms	652 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 5005;

int n;
vi adj[MXN];

ll bfs(int s) {
    ll cost = 1;
    vector<bool> visited(n+1);
    queue<pii> Q;
    visited[s] = true;
    Q.push({s, 1});
    while(!Q.empty()) {
        int u = Q.front().F, d = Q.front().S;
        Q.pop();
        for(int v : adj[u]) if(!visited[v]) {
            visited[v] = true;
            Q.push({v, d+1});
            cost += d+1;
        }
    }
    if(count(all(visited), true) != n) return 1LL*n*n;
    return cost;
}

int main() {
    FASTIO();
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int m; cin >> m;
        for(int j = 0; j < m; j++) {
            int p; cin >> p;
            adj[p].PB(i);
        }
    }
    ll ans = 1LL*n*n;
    for(int i = 1; i <= n; i++) {
        ll cost = bfs(i);
        ans = min(ans, cost);
    }
    cout << ans << "\n";
    return 0;
}

/*



*/

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