oj.uz

Submission #1018746

# Submission time Handle Problem Language Result Execution time Memory
1018746 2024-07-10T09:15:09 Z coolboy19521 Bosses (BOI16_bosses) C++17
100 / 100
 541 ms 812 KB 
#include "bits/stdc++.h"
#define int long long

using namespace std;

const int inf = 1e18 + 18;
const int sz = 5e3 + 15;

vector<int> aj[sz];
bool vi[sz];
int n;

int bfs(int x) {
	fill_n(vi, sz, false);
	queue<pair<int,int>> q;
	q.push(make_pair(1,x));
	int r = 0;
	int c = 0;

	while (!q.empty()) {
		auto tp = q.front();
		q.pop();
		int d = tp.first;
		int v = tp.second;
		if (vi[v])
			continue;
		vi[v] = true;
		r += d;
		c ++;
		for (int u : aj[v])
			if (!vi[u])
				q.push(make_pair(d + 1, u));
	}

	return (c == n ? r : inf);
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i ++) {
		int k;
		cin >> k;
		for (int j = 1; j <= k; j ++) {
			int v;
			cin >> v;
			aj[v].push_back(i);
		}
	}

	int mn = inf;

	for (int i = 1; i <= n; i ++) {
		int r = bfs(i);
		mn = min(mn, r);
	}

	cout << mn << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 14 ms 604 KB Output is correct
13 Correct 11 ms 604 KB Output is correct
14 Correct 97 ms 676 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 446 ms 812 KB Output is correct
17 Correct 511 ms 604 KB Output is correct
18 Correct 541 ms 792 KB Output is correct