답안 #108512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108512	2019-04-30T06:06:42 Z	maruii	Bosses (BOI16_bosses)	C++14	100 / 100	821 ms	836 KB

bosses

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

vector<int> edge[5001];
bool vis[5001];

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=N; ++i){
		int k; cin>>k;
		while(k--){
			int x; cin>>x;
			edge[x].push_back(i);
		}
	}
	int ans = 1e9;
	for(int i=1; i<=N; ++i){
		queue<pii> q;
		int sum = 0, cnt = 0;
		memset(vis+1, 0, N);
		q.emplace(i, 1); vis[i] = 1;
		while(q.size()){
			auto x = q.front(); q.pop();
			sum += x.ss;
			++cnt;
			for(auto i: edge[x.ff]){
				if(vis[i]) continue;
				vis[i] = 1;
				q.emplace(i, x.ss+1);
			}
		}
		if(cnt == N) ans = min(ans, sum);
	}
	cout<<ans;
	return 0;
}

Subtask #1

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	2 ms	540 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct

Subtask #2

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	2 ms	540 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	3 ms	516 KB	Output is correct
9	Correct	3 ms	484 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct

Subtask #3

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	2 ms	540 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	3 ms	516 KB	Output is correct
9	Correct	3 ms	484 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	6 ms	640 KB	Output is correct
13	Correct	6 ms	640 KB	Output is correct
14	Correct	145 ms	612 KB	Output is correct
15	Correct	6 ms	540 KB	Output is correct
16	Correct	740 ms	836 KB	Output is correct
17	Correct	762 ms	732 KB	Output is correct
18	Correct	821 ms	696 KB	Output is correct