# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
442846 |
2021-07-09T08:54:35 Z |
palilo |
Bosses (BOI16_bosses) |
C++17 |
|
709 ms |
628 KB |
#include <bits/stdc++.h>
using namespace std;
template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n;
cin >> n;
vector<vector<int>> adj(n);
for (int v = 0, u, k; v < n; ++v) {
for (cin >> k; k--;) {
cin >> u, --u;
adj[u].emplace_back(v);
}
}
vector<int> dist(n);
queue<int> q;
auto solve = [&](int root) -> int {
fill(dist.begin(), dist.end(), 0);
dist[root] = 1;
q.emplace(root);
while (!q.empty()) {
const auto u = q.front();
q.pop();
for (const auto& v : adj[u]) {
if (!dist[v]) {
dist[v] = dist[u] + 1;
q.emplace(v);
}
}
}
if (all_of(dist.begin(), dist.end(), [&](const auto& x) { return x; })) {
return accumulate(dist.begin(), dist.end(), 0);
} else {
return INT_MAX;
}
};
int ans = INT_MAX;
for (int i = 0; i < n; ++i) {
chmin(ans, solve(i));
}
assert(ans != INT_MAX);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
5 ms |
444 KB |
Output is correct |
13 |
Correct |
4 ms |
332 KB |
Output is correct |
14 |
Correct |
120 ms |
552 KB |
Output is correct |
15 |
Correct |
6 ms |
460 KB |
Output is correct |
16 |
Correct |
548 ms |
628 KB |
Output is correct |
17 |
Correct |
709 ms |
588 KB |
Output is correct |
18 |
Correct |
693 ms |
588 KB |
Output is correct |