제출 #1275665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275665		ehsan1011000	Bosses (BOI16_bosses)	C++20	100 / 100	368 ms	752 KiB

bosses

#include <bits/stdc++.h>
#include <iomanip>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,sse4")
 
using namespace std;
 
# define pb push_back
# define pf push_front
# define ff first
# define ss second
# define ll long long
# define lc id * 2
# define rc lc | 1
//# define int long long
# define mid (r + l) / 2
//# define mp make_pair
typedef long double ld;
#define kill(x)  cout << x << '\n', exit(0)
typedef pair<int, char> pic;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 5e3 + 10, maxm = 4e5 + 10, sq = 1300, LOG = 30, mod = 1e9 + 7;
const ll inf = 1e17;
int n;
vector<int> adj[maxn];
queue<int> q;
ll dist[maxn];
ll ans = inf, cnt = 0, num = 0;

void bfs(int st){
	dist[st] = 0;
	q.push(st);
	while(! q.empty()){
		int v = q.front();
		q.pop();
		num ++;
		cnt += (dist[v] + 1);
		for(int u : adj[v]){
			if(dist[v] + 1 < dist[u]){
				dist[u] = dist[v] + 1;
				q.push(u);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++){
		int k;
		cin >> k;
		for(int j = 1; j <= k; j ++){
			int v;
			cin >> v;
			adj[v].pb(i);
		}
	}
	for(int i = 1; i <= n; i ++){
		memset(dist, 63, sizeof(dist));
		cnt = num = 0;
		bfs(i);
		if(num < n) continue;
		ans = min(ans, cnt);
	}
	cout << ans << '\n';
    return 0; 
}

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