oj.uz

답안 #927123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927123 2024-02-14T09:45:55 Z pcc Bosses (BOI16_bosses) C++14
100 / 100
 413 ms 816 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 5050;
const ll inf = 1e9;
ll dist[mxn];
queue<int> q;
vector<int> paths[mxn];
int N,M;

ll BFS(int s){
	q.push(s);
	fill(dist,dist+N+1,inf);
	dist[s] = 1;
	q.push(s);
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(auto nxt:paths[now]){
			if(dist[nxt]>dist[now]+1){
				dist[nxt] = dist[now]+1;
				q.push(nxt);
			}
		}
	}
	return accumulate(dist+1,dist+N+1,0ll);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++){
		int k;
		cin>>k;
		while(k--){
			int tmp;
			cin>>tmp;
			paths[tmp].push_back(i);
		}
	}
	ll ans = inf*inf;
	for(int i = 1;i<=N;i++)ans = min(ans,BFS(i));
	cout<<ans;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 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 1 ms 356 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 580 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 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 1 ms 356 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 580 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 87 ms 704 KB Output is correct
15 Correct 21 ms 604 KB Output is correct
16 Correct 413 ms 792 KB Output is correct
17 Correct 373 ms 600 KB Output is correct
18 Correct 400 ms 816 KB Output is correct