Submission #159540

#	Time	Username	Problem	Language	Result	Execution time	Memory
159540		socho	Bosses (BOI16_bosses)	C++14	67 / 100	1568 ms	1052 KiB

bosses

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

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

int sol(int node) {
	int sb = 0;
	for (int i=0; i<sub[node].size(); i++) {
		int s = sub[node][i];
		sb += sol(s);
	}
	return tak[node] = sb + 1;
}

int boss(int mo) {
	
	int via[MXN]; 
	bool vis[MXN];
	for (int i=1; i<=n; i++) {
		via[i] = INT_MAX;
		sub[i].clear();
	}
	via[mo] = 0;
	memset(vis, 0, sizeof vis);
	
	// cout << "FOR: " << mo << endl;
	
	queue<pair<int, int> > proc; // node, via
	proc.push(make_pair(mo, -1));
	vis[mo] = true;
	while (!proc.empty()) {
		pair<int, int> pr = proc.front(); proc.pop();
		int nd = pr.first, vi = pr.second;
		// cout << " > " << nd << " via " << vi << endl;
		via[nd] = vi;
		for (int i=0; i<adj[nd].size(); i++) {
			int other = adj[nd][i];
			// cout << " ; " << other << endl;
			if (!vis[other]) {
				vis[other] = true;
				proc.push(make_pair(other, nd));
				// cout << "   : " << other << endl;
			}
		}
	} 
	
	
	for (int i=1; i<=n; i++) {
		if (via[i] == INT_MAX) return INT_MAX;
		if (via[i] == -1) continue;
		sub[via[i]].push_back(i);
	}
	
	sol(mo);
	int s = 0;
	for (int i=1; i<=n; i++) s += tak[i];
	return s;
	
}

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 sol(int)':
bosses.cpp:12:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<sub[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
bosses.cpp: In function 'int boss(int)':
bosses.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<adj[nd].size(); i++) {
                 ~^~~~~~~~~~~~~~~

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