oj.uz

Submission #640561

# Submission time Handle Problem Language Result Execution time Memory
640561 2022-09-14T23:56:17 Z ymm Bosses (BOI16_bosses) C++17
100 / 100
 579 ms 724 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 576 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 100 ms 608 KB Output is correct
15 Correct 5 ms 596 KB Output is correct
16 Correct 471 ms 692 KB Output is correct
17 Correct 579 ms 704 KB Output is correct
18 Correct 569 ms 724 KB Output is correct