Submission #58206

#	Time	Username	Problem	Language	Result	Execution time	Memory
58206		PeppaPig	Bosses (BOI16_bosses)	C++14	67 / 100	1579 ms	1880 KiB

bosses

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 5e3 + 5;

int n, ans = INT_MAX;
vector<vector<int> > g(N);
int sal[N], par[N], dep[N];

int bfs(int root) {
	int ret = 0;
	queue<int> Q;
	stack<int> S;
	for(int i = 1; i <= n; i++) sal[i] = 1, dep[i] = INT_MAX;

	Q.emplace(root);
	par[root] = 0;
	dep[root] = 1;

	while(!Q.empty()) {
		int now = Q.front();
		Q.pop();

		S.emplace(now);
		for(int v : g[now]) if(dep[now] + 1 < dep[v]) {
			dep[v] = dep[now] + 1;
			par[v] = now;
			Q.emplace(v);
		} 
	}

	vector<pii> proc;
	for(int i = 1; i <= n; i++) {
		if(dep[i] == INT_MAX) return INT_MAX;
		proc.emplace_back(dep[i], i);
	}
	sort(proc.begin(), proc.end(), [&](const pii &a, const pii &b) {
		return a.x > b.x;
	});
	for(pii v : proc) sal[par[v.y]] += sal[v.y];
	for(int i = 1; i <= n; i++) ret += sal[i];
	return ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 1, k; i <= n; i++) {
		scanf("%d", &k);
		while(k--) {
			int v;
			scanf("%d", &v);
			g[v].emplace_back(i);
		}
	} 

	for(int i = 1; i <= n; i++) ans = min(ans, bfs(i));
	printf("%d", ans);

	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
bosses.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v);
    ~~~~~^~~~~~~~~~

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