Submission #220484

#	Time	Username	Problem	Language	Result	Execution time	Memory
220484		Calico	Bosses (BOI16_bosses)	C++17	0 / 100	5 ms	640 KiB

bosses

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

int n, ans = 100000000;
vector<short> adj[5001];
vector<short> adj_tr[5001];
short dist[5001], prv[5001], vis[5001];
int dp[5001];

void dfs(short now) {
	dp[now] = 1;
	for (short u: adj_tr[now]) {
		dfs(u);
		dp[now] += dp[u];
	}
}

int bfs(short fi) {
	for (short i = 1; i <= n; i++) {
		adj_tr[i].clear();
	}
	memset(dp, 0, sizeof(dp));
	memset(dist, 0, sizeof(dist));
	memset(prv, 0, sizeof(prv));
	memset(vis, 0, sizeof(vis));

	queue<short> q;
	q.push(fi); dist[fi] = 1;

	while (q.size()) {
		short now = q.front(); q.pop();
		if (vis[now]) continue;
		vis[now] = 1;

		for (short u: adj[now]) {
			if (dist[u] == 0) {
				dist[u] = dist[now] + 1;
				q.push(u); prv[u] = now;
			}
		}
	}

	for (short i = 1; i <= n; i++) {
		if (i != fi) {
			if (prv[i] == 0) return ans;
			adj_tr[prv[i]].push_back(i);
		}
	}

	dfs(fi);
	int rs = 0;
	for (short i = 1; i <= n; i++) {
		rs += dp[i];
	}
	return rs;
}

signed main() {
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int k; scanf("%d", &k);
		while (k--) {
			short x; scanf("%d", &x);
			adj[x].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = min(ans, bfs(i));
	}
	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:64:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'short int*' [-Wformat=]
    short x; scanf("%d", &x);
                         ~~^
bosses.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:62:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
          ~~~~~^~~~~~~~~~
bosses.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    short x; scanf("%d", &x);
             ~~~~~^~~~~~~~~~

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