oj.uz

Submission #27225

# Submission time Handle Problem Language Result Execution time Memory
27225 2017-07-11T07:00:01 Z TAMREF Bosses (BOI16_bosses) C++11
100 / 100
 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

bosses.cpp: In function 'int main()':
bosses.cpp:7:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
bosses.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(scanf("%d",&a);a--;){
                           ^
bosses.cpp:10:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
                           ^

Subtask #1
22.0 / 22.0

# 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

Subtask #2
45.0 / 45.0

# 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

Subtask #3
33.0 / 33.0

# 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