oj.uz

답안 #733492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733492 2023-04-30T23:41:23 Z JellyTheOctopus Bosses (BOI16_bosses) C++17
100 / 100
 685 ms 720 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> adjList[5001];

int bfs(int root) {
	vector<bool> seen(N+1);
	queue<pair<int, int>> q; // node, depth
	q.push({root, 1}); // starting depth at one
	int ans = 0;
	int reached = 0;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		int u = cur.first;
		int depth = cur.second;
		q.pop();
		if (!seen[u]) {
			seen[u] = true;
			reached++;
			ans += depth;
			for (auto v: adjList[u]) {
				if (!seen[v]) {
					q.push({v, depth+1});
				}
			}
		}
	}
	if (reached < N) {
		return INT_MAX;
	}
	return ans;
}

int main() {
	cin >> N;
	for (int v = 1; v <= N; v++) {
		int k;
		cin >> k;
		for (int i = 0; i < k; i++) {
			int u;
			cin >> u;
			adjList[u].push_back(v);
		}
	}
	int ans = INT_MAX;
	for (int i = 1; i <= N; i++) {
		ans = min(ans, bfs(i));
	}
	cout << ans << "\n";
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 1 ms 420 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 1 ms 340 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 1 ms 340 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 23 ms 648 KB Output is correct
13 Correct 16 ms 572 KB Output is correct
14 Correct 141 ms 512 KB Output is correct
15 Correct 4 ms 432 KB Output is correct
16 Correct 546 ms 604 KB Output is correct
17 Correct 681 ms 624 KB Output is correct
18 Correct 685 ms 720 KB Output is correct