# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
485982 |
2021-11-10T03:41:08 Z |
chungdinh |
Bosses (BOI16_bosses) |
C++17 |
|
792 ms |
660 KB |
#include <iostream>
#include <utility>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define ii pair<int, int>
#define ll long long
#define MP(x, y) make_pair(x, y)
const int N = 5e3 + 5;
const ll INF = 1e18;
int n;
vector<int> g[N];
bool vsd[N];
ll dp[N];
vector<int> lst;
ll bfs(int u) {
ll res = 0;
queue<int> q; q.push(u);
memset(vsd, false, sizeof vsd); vsd[u] = true;
memset(dp, 0ll, sizeof dp); dp[u] = 1;
while (q.size()) {
int u = q.front(); q.pop();
res += dp[u];
for (int v : g[u]) {
if (!vsd[v]) {
vsd[v] = true;
q.push(v);
dp[v] = dp[u] + 1;
}
}
}
for (int i = 1; i <= n; i++) if (!vsd[i]) return INF;
return res;
}
int main() {
#ifdef CHUNGDINH
freopen("main.inp", "r", stdin);
#endif // CHUNGDINH
cin >> n;
for (int i = 1; i <= n; i++) {
int k; cin >> k;
while (k--) {
int u; cin >> u;
g[u].push_back(i);
}
}
ll res = INF;
for (int i = 1; i <= n; i++) res = min(res, bfs(i));
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
420 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
420 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
5 ms |
460 KB |
Output is correct |
13 |
Correct |
6 ms |
460 KB |
Output is correct |
14 |
Correct |
145 ms |
552 KB |
Output is correct |
15 |
Correct |
8 ms |
460 KB |
Output is correct |
16 |
Correct |
523 ms |
636 KB |
Output is correct |
17 |
Correct |
792 ms |
660 KB |
Output is correct |
18 |
Correct |
721 ms |
656 KB |
Output is correct |