# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
74901 | 2018-09-07T11:42:42 Z | Vardanyan | Bosses (BOI16_bosses) | C++14 | 635 ms | 1240 KB |
//#pragma GCC optimize "-O3" #include <bits/stdc++.h> using namespace std; const int N = 5001; vector<int> g[N]; int n; long long ans = 10000000000000005; int mark[N]; int main(){ 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); g[x].push_back(i); } } for(int i = 1;i<=n;i++){ long long val = 0; memset(mark,0,sizeof(mark)); mark[i] = 1; queue<int> q; q.push(i); int cnt = 0; while(!q.empty()){ int v = q.front(); q.pop(); cnt++; val+=mark[v]; if(val>=ans) break; for(int j = 0;j<g[v].size();j++){ int to = g[v][j]; if(mark[to]) continue; mark[to] = mark[v]+1; q.push(to); } } if(cnt == n) ans = min(ans,val); } printf("%lld\n",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 636 KB | Output is correct |
3 | Correct | 2 ms | 636 KB | Output is correct |
4 | Correct | 15 ms | 740 KB | Output is correct |
5 | Correct | 2 ms | 740 KB | Output is correct |
6 | Correct | 2 ms | 740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 636 KB | Output is correct |
3 | Correct | 2 ms | 636 KB | Output is correct |
4 | Correct | 15 ms | 740 KB | Output is correct |
5 | Correct | 2 ms | 740 KB | Output is correct |
6 | Correct | 2 ms | 740 KB | Output is correct |
7 | Correct | 2 ms | 740 KB | Output is correct |
8 | Correct | 2 ms | 740 KB | Output is correct |
9 | Correct | 2 ms | 740 KB | Output is correct |
10 | Correct | 2 ms | 740 KB | Output is correct |
11 | Correct | 2 ms | 740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 636 KB | Output is correct |
3 | Correct | 2 ms | 636 KB | Output is correct |
4 | Correct | 15 ms | 740 KB | Output is correct |
5 | Correct | 2 ms | 740 KB | Output is correct |
6 | Correct | 2 ms | 740 KB | Output is correct |
7 | Correct | 2 ms | 740 KB | Output is correct |
8 | Correct | 2 ms | 740 KB | Output is correct |
9 | Correct | 2 ms | 740 KB | Output is correct |
10 | Correct | 2 ms | 740 KB | Output is correct |
11 | Correct | 2 ms | 740 KB | Output is correct |
12 | Correct | 8 ms | 740 KB | Output is correct |
13 | Correct | 6 ms | 740 KB | Output is correct |
14 | Correct | 143 ms | 740 KB | Output is correct |
15 | Correct | 7 ms | 976 KB | Output is correct |
16 | Correct | 635 ms | 1088 KB | Output is correct |
17 | Correct | 189 ms | 1088 KB | Output is correct |
18 | Correct | 188 ms | 1240 KB | Output is correct |