oj.uz

Submission #453673

# Submission time Handle Problem Language Result Execution time Memory
453673 2021-08-04T14:20:02 Z Hamed5001 Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 5e3+10;
vector<int> edges[mxN];

int N;

int bfs(int st) {
	queue<pair<int, int>> q;
	vector<int> VIS(N+1, 0);
	VIS[st] = 1; q.push({1, st});

	int ret = 0;

	while(q.size()) {
		auto node = q.front();
		q.pop();
		VIS[node.second] = 1;
		ret += node.first;

		for (auto c : edges[node.second]) {
			if (!VIS[c])
				q.push({node.first+1, c});
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!VIS[i]) {
			ret = INT_MAX;
			break;
		}
	}
	return ret;
}

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int K;
		cin >> K;
		for (int j = 0; j < K; j++) {
			int boss;
			cin >> boss;
			edges[boss].push_back(i);
		}
	}
	int ans = INT_MAX;
	for (int i = 1; i <= N; i++)
		ans = min(ans, bfs(i));


	if (ans == INT_MAX)
		ans = -1;
	cout << ans;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -