Submission #244311

#	Time	Username	Problem	Language	Result	Execution time	Memory
244311		eohomegrownapps	Bosses (BOI16_bosses)	C++14	100 / 100	1349 ms	1144 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

vector<int> adjlist[5000];
vector<int> treeadjlist[5000];

int INF = 1e9;
int n;

int treesum = 0;

int dfs(int root){
	int tot = 1;
	for (int i : treeadjlist[root]){
		tot+=dfs(i);
	}
	treesum+=tot;
	return tot;
}

int bfs(int root){
	for (int i = 0; i<n; i++){
		treeadjlist[i].clear();
	}
	vector<bool> visited(n);
	queue<int> q;
	q.push(root);
	visited[root]=true;
	int cnt = 1;
	while (q.size()){
		int f = q.front();
		q.pop();
		for (int i : adjlist[f]){
			if (visited[i]){continue;}
			visited[i]=true;
			cnt++;
			treeadjlist[f].push_back(i);
			q.push(i);
		}
	}
	if (cnt!=n){
		return INF;
	}
	treesum=0;
	dfs(root);
	return treesum;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n;
	//adjlist.resize(n);
	for (int i = 0; i<n; i++){
		int k;
		cin>>k;
		for (int j = 0; j<k; j++){
			int x;
			cin>>x;
			x--;
			adjlist[x].push_back(i);
		}
	}
	int minval = INF;
	for (int i = 0; i<n; i++){
		minval=min(minval,bfs(i));
	}
	cout<<minval<<'\n';
}

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