# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
50114 | 2018-06-07T15:13:56 Z | MoskriLoko | Bosses (BOI16_bosses) | C++14 | 1078 ms | 1148 KB |
#include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vvi vector< vi > #define vii vector< ii > #define mp make_pair #define pb push_back const int maxn = 5005; vector<int> adj[maxn]; int n; int vis2[maxn]; int p[maxn]; int inq[maxn]; ll cost[maxn]; ll solve(int x) { memset(vis2, 0, sizeof vis2); memset(cost, 0, sizeof cost); memset(p, -1, sizeof p); vector<int> rev; queue<int> Q; Q.push(x); vis2[x] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); rev.pb(u); for(int v : adj[u]) { if(!vis2[v]) { vis2[v] = 1; p[v] = u; Q.push(v); } } } if(rev.size() != n) return 1e18; reverse(rev.begin(), rev.end()); ll tot = 0; for(int i = 0; i< (int) rev.size(); i++) { int u = rev[i]; cost[u]++; tot += cost[u]; if(p[u] != -1) cost[p[u]] += cost[u]; } return tot; } int main() { //#ifndef atom //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); //#endif scanf("%d", &n); for(int i = 1; i<= n; i++) { int k; scanf("%d", &k); for(int j = 1; j<= k; j++) { int x; scanf("%d", &x); adj[x].pb(i); } } ll best = 1e18; for(int i = 1; i<= n; i++) best = min(best, solve(i)); printf("%lld\n", best); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 668 KB | Output is correct |
3 | Correct | 2 ms | 668 KB | Output is correct |
4 | Correct | 2 ms | 668 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 668 KB | Output is correct |
3 | Correct | 2 ms | 668 KB | Output is correct |
4 | Correct | 2 ms | 668 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 668 KB | Output is correct |
7 | Correct | 2 ms | 668 KB | Output is correct |
8 | Correct | 2 ms | 752 KB | Output is correct |
9 | Correct | 2 ms | 828 KB | Output is correct |
10 | Correct | 3 ms | 828 KB | Output is correct |
11 | Correct | 3 ms | 828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 668 KB | Output is correct |
3 | Correct | 2 ms | 668 KB | Output is correct |
4 | Correct | 2 ms | 668 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 668 KB | Output is correct |
7 | Correct | 2 ms | 668 KB | Output is correct |
8 | Correct | 2 ms | 752 KB | Output is correct |
9 | Correct | 2 ms | 828 KB | Output is correct |
10 | Correct | 3 ms | 828 KB | Output is correct |
11 | Correct | 3 ms | 828 KB | Output is correct |
12 | Correct | 7 ms | 828 KB | Output is correct |
13 | Correct | 6 ms | 900 KB | Output is correct |
14 | Correct | 197 ms | 952 KB | Output is correct |
15 | Correct | 26 ms | 1144 KB | Output is correct |
16 | Correct | 793 ms | 1144 KB | Output is correct |
17 | Correct | 1078 ms | 1148 KB | Output is correct |
18 | Correct | 943 ms | 1148 KB | Output is correct |