# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
831468 | 2023-08-20T09:30:06 Z | lovrot | Bosses (BOI16_bosses) | C++17 | 612 ms | 14184 KB |
#include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <queue> #define PB push_back using namespace std; typedef long long ll; const int N = 5e5 + 10; const ll INF = 1e18; int n; vector<int> G[N]; int D[N]; queue<int> Q; ll bfs(int s) { ll res = 0; memset(D, 0, sizeof(D)); Q.push(s); D[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); res += D[u]; for(int v : G[u]) { if(D[v]) continue; D[v] = D[u] + 1; Q.push(v); } } for(int u = 1; u <= n; ++u) if(!D[u]) return INF; return res; } int main() { scanf("%d", &n); for(int u = 1; u <= n; ++u) { int k; scanf("%d", &k); for(int i = 0; i < k; ++i) { int v; scanf("%d", &v); G[v].PB(u); } } ll ans = INF; for(int u = 1; u <= n; ++u) ans = min(ans, bfs(u)); printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 13908 KB | Output is correct |
2 | Correct | 7 ms | 13960 KB | Output is correct |
3 | Correct | 7 ms | 13960 KB | Output is correct |
4 | Correct | 6 ms | 13960 KB | Output is correct |
5 | Correct | 6 ms | 13908 KB | Output is correct |
6 | Correct | 7 ms | 13964 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 13908 KB | Output is correct |
2 | Correct | 7 ms | 13960 KB | Output is correct |
3 | Correct | 7 ms | 13960 KB | Output is correct |
4 | Correct | 6 ms | 13960 KB | Output is correct |
5 | Correct | 6 ms | 13908 KB | Output is correct |
6 | Correct | 7 ms | 13964 KB | Output is correct |
7 | Correct | 10 ms | 13956 KB | Output is correct |
8 | Correct | 8 ms | 13908 KB | Output is correct |
9 | Correct | 9 ms | 14080 KB | Output is correct |
10 | Correct | 9 ms | 13908 KB | Output is correct |
11 | Correct | 10 ms | 13908 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 13908 KB | Output is correct |
2 | Correct | 7 ms | 13960 KB | Output is correct |
3 | Correct | 7 ms | 13960 KB | Output is correct |
4 | Correct | 6 ms | 13960 KB | Output is correct |
5 | Correct | 6 ms | 13908 KB | Output is correct |
6 | Correct | 7 ms | 13964 KB | Output is correct |
7 | Correct | 10 ms | 13956 KB | Output is correct |
8 | Correct | 8 ms | 13908 KB | Output is correct |
9 | Correct | 9 ms | 14080 KB | Output is correct |
10 | Correct | 9 ms | 13908 KB | Output is correct |
11 | Correct | 10 ms | 13908 KB | Output is correct |
12 | Correct | 16 ms | 14036 KB | Output is correct |
13 | Correct | 16 ms | 14052 KB | Output is correct |
14 | Correct | 255 ms | 14076 KB | Output is correct |
15 | Correct | 168 ms | 14084 KB | Output is correct |
16 | Correct | 571 ms | 14164 KB | Output is correct |
17 | Correct | 585 ms | 14184 KB | Output is correct |
18 | Correct | 612 ms | 14184 KB | Output is correct |