# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27225 | 2017-07-11T07:00:01 Z | TAMREF | Bosses (BOI16_bosses) | C++11 | 1006 ms | 2872 KB |
#include <bits/stdc++.h> using namespace std; const int mx=50005; int q[mx], bef[mx], anss[mx], v[5005], f, r, N; vector<int> G[5005]; int main(){ scanf("%d",&N); for(int i=1,a,b;i<=N;i++){ for(scanf("%d",&a);a--;){ scanf("%d",&b); G[b].push_back(i); } } long long ans=LLONG_MAX; for(int root=1,top;root<=N;root++){ f=r=1; long long tmp=0; memset(v,0,sizeof(v)); fill(anss,anss+mx,1); q[r++]=root; while(f!=r){ top=q[f]; if(v[top]){ anss[f]=0; goto yay; } v[top]=1; for(int bh : G[top]){ if(!v[bh]){ bef[r]=f; q[r++]=bh; } } yay: ++f; } if(*min_element(v+1,v+N+1)==0) continue; for(int k=r-1;k;--k){ if(!anss[k]) continue; tmp+=anss[k]; anss[bef[k]]+=anss[k]; } ans=min(ans,tmp); } printf("%lld\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2740 KB | Output is correct |
2 | Correct | 0 ms | 2740 KB | Output is correct |
3 | Correct | 0 ms | 2740 KB | Output is correct |
4 | Correct | 0 ms | 2740 KB | Output is correct |
5 | Correct | 0 ms | 2740 KB | Output is correct |
6 | Correct | 0 ms | 2740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2740 KB | Output is correct |
2 | Correct | 0 ms | 2740 KB | Output is correct |
3 | Correct | 0 ms | 2740 KB | Output is correct |
4 | Correct | 0 ms | 2740 KB | Output is correct |
5 | Correct | 0 ms | 2740 KB | Output is correct |
6 | Correct | 0 ms | 2740 KB | Output is correct |
7 | Correct | 3 ms | 2740 KB | Output is correct |
8 | Correct | 0 ms | 2740 KB | Output is correct |
9 | Correct | 0 ms | 2740 KB | Output is correct |
10 | Correct | 3 ms | 2740 KB | Output is correct |
11 | Correct | 3 ms | 2740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2740 KB | Output is correct |
2 | Correct | 0 ms | 2740 KB | Output is correct |
3 | Correct | 0 ms | 2740 KB | Output is correct |
4 | Correct | 0 ms | 2740 KB | Output is correct |
5 | Correct | 0 ms | 2740 KB | Output is correct |
6 | Correct | 0 ms | 2740 KB | Output is correct |
7 | Correct | 3 ms | 2740 KB | Output is correct |
8 | Correct | 0 ms | 2740 KB | Output is correct |
9 | Correct | 0 ms | 2740 KB | Output is correct |
10 | Correct | 3 ms | 2740 KB | Output is correct |
11 | Correct | 3 ms | 2740 KB | Output is correct |
12 | Correct | 23 ms | 2872 KB | Output is correct |
13 | Correct | 13 ms | 2872 KB | Output is correct |
14 | Correct | 319 ms | 2872 KB | Output is correct |
15 | Correct | 159 ms | 2872 KB | Output is correct |
16 | Correct | 779 ms | 2872 KB | Output is correct |
17 | Correct | 996 ms | 2872 KB | Output is correct |
18 | Correct | 1006 ms | 2872 KB | Output is correct |