Submission #159620

#	Time	Username	Problem	Language	Result	Execution time	Memory
159620		socho	Bosses (BOI16_bosses)	C++14	100 / 100	1049 ms	776 KiB

bosses

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

const int MXN = 5005;
int n;
vector<int> adj[MXN];

int boss(int mo) {
	
	bool vis[MXN];
	memset(vis, 0, sizeof vis);
	int dist[MXN];
	for (int i=0; i<MXN; i++) dist[i] = INT_MAX;
	
	queue<pair<int, int> > topr; // node, dist
	topr.push(make_pair(mo, 0));
	
	while (!topr.empty()) {
		pair<int, int> nx = topr.front(); topr.pop();
		int node = nx.first, dis = nx.second;
		dist[node] = dis;
		vis[node] = true;
		for (int i=0; i<adj[node].size(); i++) {
			int other = adj[node][i];
			if (!vis[other]) {
				vis[other] = true;
				topr.push(make_pair(other, dis+1));
			}
		}
	}
	
	int sm = 0;
	
	for (int i=1; i<=n; i++) {
		if (dist[i] == INT_MAX) return INT_MAX;
		sm += (dist[i] + 1);
	}
	return sm;
}

int main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for (int i=1; i<=n; i++) {
		int ac;
		cin >> ac;
		for (int j=0; j<ac; j++) {
			int k;
			cin >> k;
			adj[k].push_back(i);
		}
	}
	
	int best = INT_MAX;
	for (int i=1; i<=n; i++) {
		best = min(best, boss(i));
	}
	cout << best << endl;
	
   
}

Compilation message (stderr)

bosses.cpp: In function 'int boss(int)':
bosses.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<adj[node].size(); i++) {
                 ~^~~~~~~~~~~~~~~~~

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