Submission #197532

#	Time	Username	Problem	Language	Result	Execution time	Memory
197532		dndhk	Bosses (BOI16_bosses)	C++14	100 / 100	982 ms	796 KiB

bosses

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 5000;
const int INF = 100000;
int N;
vector<int> gp[MAX_N+1];
int dist[MAX_N+1];
deque<int> dq;
int ans;

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		int x, y;
		scanf("%d", &x);
		while(x--){
			scanf("%d", &y);
			gp[y].pb(i);
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			dist[j] = INF;
		}
		dist[i] = 1;
		dq.pb(i);
		while(!dq.empty()){
			int now = dq.front(); dq.pop_front();
			for(int i : gp[now]){
				if(dist[i]>dist[now]+1){
					dist[i] = dist[now]+1;
					dq.pb(i);
				}
			}
		}
		int sum = 0;
		for(int j=1; j<=N; j++){
			sum+=dist[j];
		}
		if(i==1)	ans = sum;
		else ans = min(sum, ans);
	}
	cout<<ans;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bosses.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
bosses.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
    ~~~~~^~~~~~~~~~

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