# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106179 | 2019-04-17T05:29:04 Z | dupreez | Bosses (BOI16_bosses) | C++14 | 671 ms | 768 KB |
#include <iostream> #include <algorithm> #include <cstring> #include <sstream> #include <map> #include <queue> #include <vector> #include <stack> #include <unordered_map> #include <climits> #define mk make_pair #define pb push_back #define scanf scanf_s using namespace std; typedef long long int ll; typedef short int ui; typedef unsigned long long int ull; const int N = 5010; int n; ll ans; vector<int> g[N]; int main() { cin >> n; ans = LONG_MAX; for (int i = 1; i <= n; i++) { int v1; cin >> v1; while (v1--) { int v2; cin >> v2; g[v2].pb(i); } } for (int i = 1; i <= n; i++) { ll cv = 0,dpt[N],ct=0; memset(dpt, -1, sizeof(dpt)); dpt[i] = 1; queue<int> q; q.push(i); while (!q.empty()) { int ci = q.front(); q.pop(); cv += dpt[ci]; ct++; for (int i = 0; i < g[ci].size(); i++) { int ni = g[ci][i]; if (dpt[ni] != -1)continue; dpt[ni] = dpt[ci] + 1; q.push(ni); } } if(ct==n) ans = min(ans, cv); } cout << ans << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 412 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 412 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 9 ms | 512 KB | Output is correct |
13 | Correct | 9 ms | 640 KB | Output is correct |
14 | Correct | 139 ms | 640 KB | Output is correct |
15 | Correct | 15 ms | 512 KB | Output is correct |
16 | Correct | 622 ms | 704 KB | Output is correct |
17 | Correct | 605 ms | 732 KB | Output is correct |
18 | Correct | 671 ms | 768 KB | Output is correct |