Submission #1209844

#TimeUsernameProblemLanguageResultExecution timeMemory
1209844ml_tssBosses (BOI16_bosses)C++20
100 / 100
664 ms896 KiB
#include <bits/stdc++.h> using namespace std; int cost_and_check(int root, const unordered_map<int, vector<int>>& constraint, int n) { vector<int> dist(n, -1); queue<int> q; dist[root] = 1; q.push(root); while (!q.empty()) { int u = q.front(); q.pop(); if (constraint.count(u)) { for (int v : constraint.at(u)) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } } for (int d : dist) if (d == -1) return INT_MAX; int sum = 0; for (int d : dist) sum += d; return sum; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; unordered_map<int, vector<int>> um; for (int i = 0; i < N; i++) { um[i] = {}; } for (int i = 0; i < N; i++) { int c; cin >> c; for (int j = 0; j < c; j++) { int t; cin >> t; t--; um[t].push_back(i); } } int mini = INT_MAX; for (int root = 0; root < N; root++) { int val = cost_and_check(root, um, N); if (val < mini) mini = val; } cout << mini; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...