Submission #257187

#	Time	Username	Problem	Language	Result	Execution time	Memory
257187		maximath_1	Bosses (BOI16_bosses)	C++11	100 / 100	1197 ms	892 KiB

bosses

#include <iostream>
#include <queue>
#include <bitset>
#include <algorithm>

using namespace std;

int n;
vector<int> adj[5005], order, par, sz;
queue<int> bfs;
bitset<5005> vis;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for(int sz, i = 1; i <= n; i ++){
		cin >> sz;
		for(int p, j = 1; j <= sz; j ++){
			cin >> p;
			adj[p].push_back(i);
		}
	}
	par.resize(n + 1);

	int ans = 1e9 + 69;
	for(int i = 1; i <= n; i ++){ //let i be the boss
		vis = 0; order.clear();
		bfs.push(i); vis[i] = 1;
		for(; !bfs.empty(); bfs.pop()){
			int nw = bfs.front();
			order.push_back(nw);
			for(int nx : adj[nw]) if(!vis[nx]){
				vis[nx] = 1; bfs.push(nx);
				par[nx] = nw;
			}
		}

		if(order.size() != n) continue;
		reverse(order.begin(), order.end());
		int tmp = 0;
		sz.assign(n + 1, 0);
		for(int nw : order){
			sz[nw] ++; tmp += sz[nw];
			if(nw != i)
				sz[par[nw]] += sz[nw];
		}

		ans = min(ans, tmp);
	}

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(order.size() != n) continue;
      ~~~~~~~~~~~~~^~~~

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