Submission #368051

#	Time	Username	Problem	Language	Result	Execution time	Memory
368051		urd05	Bosses (BOI16_bosses)	C++14	100 / 100	748 ms	748 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[5000];
int dist[5000];
 
int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++) {
            int x;
            scanf("%d",&x);
            x--;
            adj[x].push_back(i);
        }
    }
    int ret=1e9;
    for(int r=0;r<n;r++) {
        memset(dist,-1,sizeof(dist));
        int sum=0;
        queue<int> q;
        dist[r]=0;
        q.push(r);
        while (!q.empty()) {
            int now=q.front();
            q.pop();
            for(int i=0;i<adj[now].size();i++) {
                int nt=adj[now][i];
                if (dist[nt]==-1) {
                    dist[nt]=dist[now]+1;
                    q.push(nt);
                }
            }
        }
        for(int i=0;i<n;i++) {
            sum+=dist[i];
            if (dist[i]==-1) {
                sum=1e9;
            }
        }
        ret=min(ret,sum);
    }
    printf("%d",n+ret);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int i=0;i<adj[now].size();i++) {
      |                         ~^~~~~~~~~~~~~~~~
bosses.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
bosses.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
bosses.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33