# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
254712 |
2020-07-30T13:29:06 Z |
alrad |
Bosses (BOI16_bosses) |
C++17 |
|
879 ms |
888 KB |
#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
template <class T> inline T gcd(T a , T b) { return !a ? b : gcd(b % a , a); }
template <class T> inline T lcm(T a , T b) {return (a * b) / gcd(a , b) ; }
#define all(x) x.begin(), x.end()
#define debug(x) { cerr << #x << " = " << x << endl; }
const int N = 5000 + 5;
const int INF = 1e9;
vector<vector<int> > g(N , vector<int>());
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
g[x].push_back(i);
}
}
auto calc = [&](int root) {
int sz = 1;
queue<int> q;
vector<int> d(n + 1 , 0);
vector<bool> used(n + 1 , false);
d[root] = 0 , used[root] = true , q.push(root);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : g[v]) {
if (!used[to]) {
sz++;
used[to] = true;
d[to] = d[v] + 1;
q.push(to);
}
}
}
if (sz != n) {
return INF;
}
vector<int> cnt(n + 1 , 0);
for (int i = 1; i <= n; i++) {
cnt[d[i]]++;
}
int res = 0 , children = 0;
for (int deep = n - 1; deep >= 0; deep--) {
res += children + cnt[deep];
children += cnt[deep];
}
return res;
};
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans , calc(i));
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
0 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
0 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
0 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
0 ms |
512 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
512 KB |
Output is correct |
9 |
Correct |
0 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
0 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
0 ms |
512 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
512 KB |
Output is correct |
9 |
Correct |
0 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
512 KB |
Output is correct |
14 |
Correct |
137 ms |
512 KB |
Output is correct |
15 |
Correct |
23 ms |
640 KB |
Output is correct |
16 |
Correct |
581 ms |
760 KB |
Output is correct |
17 |
Correct |
849 ms |
760 KB |
Output is correct |
18 |
Correct |
879 ms |
888 KB |
Output is correct |