Submission #1135007

#TimeUsernameProblemLanguageResultExecution timeMemory
1135007SulABosses (BOI16_bosses)C++20
100 / 100
441 ms736 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ulong unsigned long long
#define uint unsigned int

vector<int> adj[5000];
int dist[5000];

void bfs(int s) {
    fill(dist, dist + 5000, -1);
    dist[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n; cin>>n;
    for (int i = 0; i < n; i++) {
        int k; cin>>k;
        while (k--) {
            int u; cin>>u;
            adj[--u].push_back(i);
        }
    }
    long long ans = 1e18;
    for (int i = 0; i < n; i++) {
        bfs(i);
        long long cur = 0;
        for (int j = 0; j < n; j++) {
            cur = dist[j] == -1 ? 1e18 : cur + dist[j];
            if (cur == 1e18) break;
        }
        ans = min(ans, cur);
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...