Submission #1091267

#TimeUsernameProblemLanguageResultExecution timeMemory
1091267owieczkaBosses (BOI16_bosses)C++17
100 / 100
584 ms3820 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long bitset<5'001> o[5001]; ll odl [5001]; vector<int> g[5'001]; queue<pair<int, int>> qu; ll bfs(int it) { qu.push({it, 0}); odl[it] = 1; ll w = 0; while (!qu.empty()) { auto v = qu.front(); qu.pop(); if (o[it][v.first])continue; o[it][v.first] = 1; odl[v.first] = odl[v.second] + 1; w += odl[v.first]; for (auto i : g[v.first]) { if (!o[it][i])qu.push({i, v.first}); } } return w; } bitset<5'001> prawda; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, a, b; ll m = LLONG_MAX; cin >> n; for (int i = 1; i <= n; i++) { cin >> a; while (a--) { cin >> b; g[b].push_back(i); } prawda[i] = 1; } for (int i = 1; i <= n; i++) { //m = min(bfs(i), m); auto sk = bfs(i); if (o[i] == prawda)m = min(sk, m); } cout << m << '\n'; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...