제출 #569154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569154		beaconmc	Bosses (BOI16_bosses)	C++14	100 / 100	1296 ms	872 KiB

bosses

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;
ll n;
vector<vector<ll>> edges;

vector<ll> newedges[5001];


ll sum = 0;


int dfs(ll a){

	ll sus = 1;
	for (auto&i : newedges[a]){
		sus += dfs(i);
	}
	sum += sus;
	return sus;
}

ll solve(ll a){
	FOR(i,0,5001){
		newedges[i].clear();
	}

	vector<bool> visited(n+1);

	queue<ll> q;
	q.push(a);
	visited[a] = 1;

	while (q.size()){
		ll node = q.front();
		q.pop();
		for (auto&i : edges[node]){
			if (!visited[i]){
				q.push(i);
				visited[i] = 1;
				newedges[node].push_back(i);
			}
		}
	}
	sum = 0;
	dfs(a);
	FOR(i,1,n+1){
		if (!visited[i]) return 1000000000;
	}
	return sum;
}




int main(){
	cin >> n;
	FOR(i,0,n+1) edges.push_back({});

	FOR(i,0,n){
		ll temp; cin >> temp;
		FOR(j,0,temp){
			ll sus;
			cin >> sus;
			edges[sus].push_back(i+1);
		}
	}
	ll mini = 1000000000;
	FOR(i,1,n+1){
		mini = min(mini, solve(i));

	}
	cout << mini;
}

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