제출 #1153092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153092		antonn	Bosses (BOI16_bosses)	C++20	100 / 100	366 ms	740 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e3 + 7;

vector<int> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int k; 
        cin >> k;
        int mn = 1e9, sol = 0;
        for (int j = 1; j <= k; ++j) {
            int x; 
            cin >> x;
            g[x].push_back(i);
        }
    }
    ll ans = 1e18;
    for (int r = 1; r <= n; ++r) {
        vector<int> dist(n + 1, 0);
        dist[r] = 1;
        queue<int> q;
        q.push(r);
        int cnt = 1;
        ll sum = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : g[u]) {
                if (dist[v] == 0) {
                    dist[v] = dist[u] + 1;
                    sum += dist[v];
                    ++cnt;
                    q.push(v);
                }
            } 
        }
        if (cnt == n && sum == 7) cout << "! " << r << "\n";
        if (cnt == n) ans = min(ans, sum);
    }
    cout << ans << "\n";
    return 0;
}

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