제출 #1346319

#제출 시각아이디문제언어결과실행 시간메모리
1346319tamir1Bosses (BOI16_bosses)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;


#define int long long
#define ff first
#define ss second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back


vector<vector<int>> adj;
int n;

void bfs(int node, vector<int> &dist) {
    dist.assign(n, -1);
    queue<int> q;
    q.push(node);
    dist[node] = 0;
    while(!q.empty()) {
        int node = q.front(); q.pop();


        for(int v : adj[node]) {
            if(dist[v] == -1) {
                dist[v] = dist[node] + 1;
                q.push(v);
            }
        }
    }
}


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

    cin >> n;
    adj.assign(n, {});
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        while(k--) {
            int u;
            cin >> u;
            u--;
            adj[u].pb(i);
        }
    }
    vector<vector<int>> dist(n);
    int ans = 1e18;
    for(int i = 0; i < n; i++) {
        bfs(i, dist[i]);
        int mx = -1, cnt = 0;
        for(int j = 0; j < n; j++) {
            if(dist[i][j] == -1) {
                mx = -1;
                break;
            }
            if(mx < dist[i][j]) {
                mx = dist[i][j];
                cnt = 1;
            } else if(mx == dist[i][j]) cnt++;
        }
        if(mx == -1) continue;
        // cout << mx << " " << cnt << "\n";
        ans = min(ans, (n + n + 1 - mx) * mx / 2 + cnt);
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...