Submission #567687

#	Time	Username	Problem	Language	Result	Execution time	Memory
567687		Garguy22	Bosses (BOI16_bosses)	C++17	100 / 100	1405 ms	920 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9 + 7;

vector<int> adj[5007], nex[5007];
bool vis[5007];
int val[5007];

void dfs(int u){
	int temp = 0;
	for(auto v : nex[u]){
		dfs(v);
		temp += val[v];
	}
	val[u] = temp + 1;
}

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		int k;
		cin >> k;
		while(k--){
			int temp;
			cin >> temp;
			adj[temp].push_back(i);
		}
	}
	int ans = INF;
	for(int i = 1; i <= n; i++){
		vis[i] = 1;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int u = q.front();
			q.pop();
			for(auto v : adj[u]){
				if(!vis[v]){
					nex[u].push_back(v);
					vis[v] = 1;
					q.push(v);
				}
			}
		}
		bool chk = 1;
		for(int j = 1; j <= n; j++){
			if(!vis[j]){
				chk = 0;
				break;
			}
		}
		if(chk){
			dfs(i);
			int sum = 0;
			for(int j = 1; j <= n; j++)
				sum += val[j];
			ans = min(ans, sum);
		}
		for(int j = 1; j <= n; j++){
			vis[j] = 0;
			nex[j].clear();
		}
	}
	cout << ans << endl;

	return 0;
}

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