# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1014636 | 2024-07-05T08:36:21 Z | t_holl | Bosses (BOI16_bosses) | C++14 | 549 ms | 872 KB |
#include <bits/stdc++.h> #define int long long #define MULTITEST false using namespace std; using idata = vector<int>; using igrid = vector<idata>; igrid roads; idata bfs_states; int i_state = 0; idata distances; int bfs (int start) { i_state ++; int cnt = 1; queue<int> q; q.push(start); bfs_states[start] = i_state; distances [start] = 0; while (q.size() != 0) { int curr = q.front(); q.pop(); for (int next : roads[curr]) { if (bfs_states[next] == i_state) continue ; bfs_states[next] = i_state; distances [next] = distances[curr] + 1; q.push(next); cnt ++; } } if (cnt != roads.size()) return 1e18; int res = 0; for (int u : distances) res += u + 1; return res; } void solve () { int N; cin >> N; roads .resize(N); distances .resize(N); bfs_states.resize(N); for (int i = 0; i < N; i ++) { int k; cin >> k; for (int j = 0; j < k; j ++) { int n; cin >> n; roads[n - 1].push_back(i); } } int res = 1e18; for (int i = 0; i < N; i ++) res = min(res, bfs(i)); cout << res << "\n"; } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int T = 1; if (MULTITEST) cin >> T; for (int t = 0; t < T; t ++) solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 344 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 4 ms | 600 KB | Output is correct |
13 | Correct | 2 ms | 604 KB | Output is correct |
14 | Correct | 87 ms | 756 KB | Output is correct |
15 | Correct | 2 ms | 604 KB | Output is correct |
16 | Correct | 442 ms | 872 KB | Output is correct |
17 | Correct | 540 ms | 860 KB | Output is correct |
18 | Correct | 549 ms | 848 KB | Output is correct |