제출 #1275686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275686		mhn_neek	Bosses (BOI16_bosses)	C++20	100 / 100	392 ms	792 KiB

bosses

// IN THE NAME OF GOD
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 5e5 + 100;
const lli INF = 1e18;
const lli mod = 1e9 + 7;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define FOR(x,y) for(lli x = 0; x < y; x ++)
#define FORS(x,y) for(lli x = 1; x <= y; x ++)
#define all(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
#define debug(x) cerr<<(#x)<<" "<<x<<endl
lli n;
ve adj[N];
lli dis[N];

lli BFS(lli v){
	FORS(i,n)dis[i] = INF;
	queue<lli> Q;
	Q.push(v);
	dis[v] = 0;

	while (Q.size()){
		lli u = Q.front();
		Q.pop();
		for(auto i : adj[u]){
			if(dis[i] == INF){
				dis[i] = dis[u]  +1;
				Q.push(i);
			}
		}
	}
	lli ans = n;
	FORS(i,n){
		if(dis[i] == INF)return INF;
		ans += dis[i];
	}
	return ans;
	
}


int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	FORS(v,n){
		lli k;
		cin>>k;
		FOR(j,k){
			lli x;
			cin>>x;
			adj[x].PB(v);
		}
	}
	lli ans = INF;
	FORS(v,n){
		ans = min(ans,BFS(v));
	}
	cout<<ans<<endl;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33