# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106071 | 2019-04-16T10:49:39 Z | eriksuenderhauf | Bosses (BOI16_bosses) | C++11 | 841 ms | 6040 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 2e5 + 5; const double eps = 1e-9; vi adj[MAXN]; int d[MAXN], n; int solve(int root) { memset(d, 0x3f, sizeof d); int ret = 1; deque<int> pq; pq.pb(root); d[root] = 1; while (!pq.empty()) { int u = pq.front(); pq.pop_front(); for (int v: adj[u]) { if (d[v] <= d[u] + 1) continue; d[v] = d[u] + 1; ret += d[v]; pq.pb(v); } } for (int i = 0; i < n; i++) if (d[i] == 1061109567) return INF; return ret; } int main() { ni(n); for (int i = 0; i < n; i++) { int k; ni(k); for (int j = 0; j < k; j++) { int u; ni(u); u--; adj[u].pb(i); } } int ans = INF; for (int i = 0; i < n; i++) ans = min(ans, solve(i)); printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5860 KB | Output is correct |
2 | Correct | 8 ms | 5760 KB | Output is correct |
3 | Correct | 7 ms | 5852 KB | Output is correct |
4 | Correct | 9 ms | 5760 KB | Output is correct |
5 | Correct | 8 ms | 5760 KB | Output is correct |
6 | Correct | 9 ms | 5760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5860 KB | Output is correct |
2 | Correct | 8 ms | 5760 KB | Output is correct |
3 | Correct | 7 ms | 5852 KB | Output is correct |
4 | Correct | 9 ms | 5760 KB | Output is correct |
5 | Correct | 8 ms | 5760 KB | Output is correct |
6 | Correct | 9 ms | 5760 KB | Output is correct |
7 | Correct | 11 ms | 5832 KB | Output is correct |
8 | Correct | 12 ms | 5760 KB | Output is correct |
9 | Correct | 9 ms | 5888 KB | Output is correct |
10 | Correct | 12 ms | 5880 KB | Output is correct |
11 | Correct | 13 ms | 5812 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5860 KB | Output is correct |
2 | Correct | 8 ms | 5760 KB | Output is correct |
3 | Correct | 7 ms | 5852 KB | Output is correct |
4 | Correct | 9 ms | 5760 KB | Output is correct |
5 | Correct | 8 ms | 5760 KB | Output is correct |
6 | Correct | 9 ms | 5760 KB | Output is correct |
7 | Correct | 11 ms | 5832 KB | Output is correct |
8 | Correct | 12 ms | 5760 KB | Output is correct |
9 | Correct | 9 ms | 5888 KB | Output is correct |
10 | Correct | 12 ms | 5880 KB | Output is correct |
11 | Correct | 13 ms | 5812 KB | Output is correct |
12 | Correct | 19 ms | 5888 KB | Output is correct |
13 | Correct | 20 ms | 5888 KB | Output is correct |
14 | Correct | 339 ms | 5960 KB | Output is correct |
15 | Correct | 211 ms | 5880 KB | Output is correct |
16 | Correct | 760 ms | 6040 KB | Output is correct |
17 | Correct | 795 ms | 6016 KB | Output is correct |
18 | Correct | 841 ms | 6016 KB | Output is correct |