# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
23016 | 2017-05-01T17:30:18 Z | sampriti | Bosses (BOI16_bosses) | C++14 | 913 ms | 2204 KB |
#include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <climits> using namespace std; vector<int> G[5001]; int D[5001]; int curr_ans; queue<pair<int, int> > Q; int main() { int N; scanf("%d", &N); for(int i = 1; i <= N; i++) { int K; scanf("%d", &K); while(K--) { int x; scanf("%d", &x); G[x].push_back(i); } } int ans = INT_MAX; for(int i = 1; i <= N; i++) { memset(D, 0, sizeof D); Q.push({i, 0}); while(!Q.empty()) { int u = Q.front().first, p = Q.front().second; Q.pop(); if(D[u]) continue; D[u] = D[p] + 1; for(int v: G[u]) { if(D[v]) continue; Q.push({v, u}); } } bool valid = true; for(int j = 1; j <= N; j++) { if(!D[j]) { valid = false; break; } } if(!valid) continue; int curr_ans = 0; for(int j = 1; j <= N; j++) curr_ans += D[j]; ans = min(ans, curr_ans); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2072 KB | Output is correct |
2 | Correct | 0 ms | 2072 KB | Output is correct |
3 | Correct | 0 ms | 2072 KB | Output is correct |
4 | Correct | 0 ms | 2072 KB | Output is correct |
5 | Correct | 0 ms | 2072 KB | Output is correct |
6 | Correct | 0 ms | 2072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2072 KB | Output is correct |
2 | Correct | 0 ms | 2072 KB | Output is correct |
3 | Correct | 0 ms | 2072 KB | Output is correct |
4 | Correct | 0 ms | 2072 KB | Output is correct |
5 | Correct | 0 ms | 2072 KB | Output is correct |
6 | Correct | 0 ms | 2072 KB | Output is correct |
7 | Correct | 0 ms | 2072 KB | Output is correct |
8 | Correct | 0 ms | 2072 KB | Output is correct |
9 | Correct | 0 ms | 2072 KB | Output is correct |
10 | Correct | 0 ms | 2072 KB | Output is correct |
11 | Correct | 0 ms | 2072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2072 KB | Output is correct |
2 | Correct | 0 ms | 2072 KB | Output is correct |
3 | Correct | 0 ms | 2072 KB | Output is correct |
4 | Correct | 0 ms | 2072 KB | Output is correct |
5 | Correct | 0 ms | 2072 KB | Output is correct |
6 | Correct | 0 ms | 2072 KB | Output is correct |
7 | Correct | 0 ms | 2072 KB | Output is correct |
8 | Correct | 0 ms | 2072 KB | Output is correct |
9 | Correct | 0 ms | 2072 KB | Output is correct |
10 | Correct | 0 ms | 2072 KB | Output is correct |
11 | Correct | 0 ms | 2072 KB | Output is correct |
12 | Correct | 16 ms | 2204 KB | Output is correct |
13 | Correct | 13 ms | 2204 KB | Output is correct |
14 | Correct | 166 ms | 2204 KB | Output is correct |
15 | Correct | 3 ms | 2204 KB | Output is correct |
16 | Correct | 746 ms | 2204 KB | Output is correct |
17 | Correct | 913 ms | 2204 KB | Output is correct |
18 | Correct | 903 ms | 2204 KB | Output is correct |