Submission #329583

#TimeUsernameProblemLanguageResultExecution timeMemory
329583gustasonBosses (BOI16_bosses)C++14
0 / 100
1 ms492 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxN = 5005; const int INF = 1e9 + 5; vector<int> adj[maxN]; int n; int biggest_dep_1 = 0; int solve(int root) { vector<int> dep[n+1]; // vertices that are at some depth vector<int> new_adj[n+1]; vector<bool> conn(n+1, false); // is vertex already used conn[root] = true; dep[1].push_back(root); for(int d = 1; d < n; d++) { for(int v : dep[d]) { for(int u : adj[v]) { if (!conn[u]) { new_adj[u].push_back(v); dep[d+1].push_back(u); conn[u] = true; } } } if (d == 1) { if ((int) dep[2].size() < biggest_dep_1 + 5) return INF; biggest_dep_1 = (int) dep[2].size(); } } if (count(conn.begin(), conn.end(), true) != n) return INF; vector<int> sal(n+1, 0); int sum = 0; for(int d = n; d >= 1; d--) { for(int ord : dep[d]) { sal[ord]++; sum += sal[ord]; for(int boss : new_adj[ord]) { sal[boss] += sal[ord]; } } } return sum; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for(int ord = 1; ord <= n; ord++) { int k; cin >> k; for(int j = 0; j < k; j++) { int boss; cin >> boss; adj[boss].push_back(ord); } } int best = INF; // root the tree at every possible vertex for(int boss = 1; boss <= n; boss++) { best = min(best, solve(boss)); } cout << best; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...