Submission #41138

#	Time	Username	Problem	Language	Result	Execution time	Memory
41138		ssnsarang2023	Bosses (BOI16_bosses)	C++14	67 / 100	1530 ms	1628 KiB

bosses

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define SZ(x) ((int)x.size())

const int N = 5e3+5;
int n, sz[N];
bool vis[N];
vector<int> g[N], g2[N];

void dfs(int u, int &total) {
	sz[u] = 1;
	for (int v : g2[u]) {
		dfs(v, total);
		sz[u] += sz[v];
	}
	total += sz[u];
}

int make_tree(int root) {
	for (int i = 1; i <= n; ++i) vis[i] = false, g2[i].clear();
	queue<int> q;
	q.push(root);
	vis[root] = 1;
	int cnt = 1;
	while (SZ(q)) {
		int u = q.front(); q.pop();
		for (int v : g[u]) {
			if (vis[v]) continue;
			++cnt, vis[v] = true;
			q.push(v);
			g2[u].push_back(v);
		}
	}
	if (cnt < n) return (int)1e9+7;
	int sum = 0;
	dfs(root, sum);
	return sum;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int m; scanf("%d", &m);
		for (int j = 1, v; j <= m; ++j) {
			scanf("%d", &v);
			g[v].push_back(i);
		}
	}
	int res = (int)1e9+7;
	for (int i = 1; i <= n; ++i)
		res = min(res, make_tree(i));
	printf("%d", res);
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:48:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:50:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int m; scanf("%d", &m);
                         ^
bosses.cpp:52:19: 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