# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
81071 | 2018-10-23T16:18:43 Z | xiaowuc1 | Bosses (BOI16_bosses) | C++14 | 578 ms | 1444 KB |
#include <bits/stdc++.h> /* unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count(); mt19937 g1.seed(seed1); ios_base::sync_with_stdio(false); cin.tie(NULL); */ using namespace std; const double PI = 2 * acos(0); typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<int, ll> pill; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<vector<ll>> matrix; int n; vector<int> edges[5005]; int dist[5005]; int q[5005]; int solve(int curr) { for(int i = 1; i <= n; i++) { dist[i] = 1 << 25; } dist[curr] = 0; int ql = 0; int qr = 0; q[qr++] = curr; int ret = 0; while(ql < qr) { curr = q[ql++]; ret += dist[curr]; for(int out: edges[curr]) { if(dist[out] == 1 << 25) { dist[out] = dist[curr] + 1; q[qr++] = out; } } } if(ql != n) ret = 1 << 30; return ret; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { int k; scanf("%d", &k); while(k--) { int t; scanf("%d", &t); edges[t].push_back(i); } } int ret = 1 << 30; for(int i = 1; i <= n; i++) { ret = min(ret, solve(i)); } printf("%d\n", ret + n); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 640 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 640 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 660 KB | Output is correct |
7 | Correct | 2 ms | 660 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 760 KB | Output is correct |
11 | Correct | 3 ms | 912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 640 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 640 KB | Output is correct |
5 | Correct | 2 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 660 KB | Output is correct |
7 | Correct | 2 ms | 660 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 760 KB | Output is correct |
11 | Correct | 3 ms | 912 KB | Output is correct |
12 | Correct | 7 ms | 920 KB | Output is correct |
13 | Correct | 6 ms | 956 KB | Output is correct |
14 | Correct | 116 ms | 1136 KB | Output is correct |
15 | Correct | 17 ms | 1188 KB | Output is correct |
16 | Correct | 545 ms | 1300 KB | Output is correct |
17 | Correct | 578 ms | 1416 KB | Output is correct |
18 | Correct | 567 ms | 1444 KB | Output is correct |