Submission #640561

#	Time	Username	Problem	Language	Result	Execution time	Memory
640561		ymm	Bosses (BOI16_bosses)	C++17	100 / 100	579 ms	724 KiB

bosses

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 5010;
vector<int> A[N];
int dis[N];
int n;

ll bfs(int s)
{
	memset(dis, 0, sizeof(dis));
	dis[s] = 1;
	vector<int> q(1, s);
	ll ans = 1;
	for (int i = 0; i < q.size(); ++i) {
		int v = q[i];
		for (int u : A[v]) {
			if (!dis[u]) {
				dis[u] = dis[v] + 1;
				ans += dis[u];
				q.push_back(u);
			}
		}
	}
	return q.size() == n? ans: (ll)1e18;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (v,0,n) {
		int k;
		cin >> k;
		while (k--) {
			int u;
			cin >> u;
			A[u-1].push_back(v);
		}
	}
	ll ans = 1e18;
	Loop (v,0,n)
		ans = min(ans, bfs(v));
	cout << ans << '\n';
}

Compilation message (stderr)

bosses.cpp: In function 'll bfs(int)':
bosses.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 0; i < q.size(); ++i) {
      |                  ~~^~~~~~~~~~
bosses.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  return q.size() == n? ans: (ll)1e18;
      |         ~~~~~~~~~^~~~

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