Submission #41141

#	Time	Username	Problem	Language	Result	Execution time	Memory
41141		ssnsarang2023	Bosses (BOI16_bosses)	C++14	100 / 100	695 ms	1132 KiB

bosses

#include <cstdio>
#include <vector>

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], par[N];
bool vis[N];
vector<int> g[N];
int lo, hi, q[N];

int make_tree(int root) {
	for (int i = 1; i <= n; ++i) vis[i] = sz[i] = 0;
	q[1] = root;
	vis[root] = lo = hi = 1;
	int cnt = 1;
	while (lo <= hi) {
		int u = q[lo++];
		for (int i = 0; i < SZ(g[u]); ++i) {
			int v = g[u][i];
			if (vis[v]) continue;
			++cnt, vis[v] = true;
			q[++hi] = v;
			par[v] = u;
		}
	}
	if (cnt < n) return (int)1e9+7;
	int sum = 0;
	sz[0] = 0;
	for (int i = hi; i >= 1; --i) {
		++sz[q[i]];
		sz[par[q[i]]] += sz[q[i]];
		sum += sz[q[i]];
	}
	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 make_tree(int)':
bosses.cpp:18:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  for (int i = 1; i <= n; ++i) vis[i] = sz[i] = 0;
                                      ^
bosses.cpp:20:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  vis[root] = lo = hi = 1;
            ^
bosses.cpp: In function 'int main()':
bosses.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:46: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:48: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: 33 / 33