Submission #27225

#	Time	Username	Problem	Language	Result	Execution time	Memory
27225		TAMREF	Bosses (BOI16_bosses)	C++11	100 / 100	1006 ms	2872 KiB

bosses

#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 (stderr)

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33