Submission #498460

#	Time	Username	Problem	Language	Result	Execution time	Memory
498460		dsyz	Bosses (BOI16_bosses)	C++17	100 / 100	733 ms	716 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	vector<ll> v[N];
	for(ll i = 0;i < N;i++){
		ll k;
		cin>>k;
		for(ll j = 0;j < k;j++){
			ll a;
			cin>>a;
			a--;
			v[a].push_back(i);
		}
	}
	ll sum = 1000000000000005;
	queue<ll> q;
	ll dist[N];
	int visited[N];
	for(ll i = 0;i < N;i++){
		memset(dist,0,sizeof(dist));
		memset(visited,0,sizeof(visited));
		q.push(i);
		dist[i] = 0;
		visited[i] = 1;
		while(!q.empty()){
			ll a = q.front();
			q.pop();
			for(auto u : v[a]){
				if(visited[u] == 0 || dist[u] > dist[a] + 1){
					q.push(u);
					dist[u] = dist[a] + 1;
					visited[u] = 1;
				}
			}
		}
		ll no = 0;
		ll total = 0;
		for(ll i = 0;i < N;i++){
			if(visited[i] == 0){
				no = 1;
				break;
			}
			total += dist[i] + 1;
		}
		if(no == 0) sum = min(sum,total);
	}
	cout<<sum<<'\n';
}

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