Submission #446226

#	Time	Username	Problem	Language	Result	Execution time	Memory
446226		mariowong	Bosses (BOI16_bosses)	C++14	100 / 100	1340 ms	684 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

int n,x,u,ans,boss[5005],sum[5005],now,summm;
bool vis[5005];
vector <int> edge[5005];
queue <int> q;
stack<int> s;
int main(){
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> x;
		for (int j=1;j<=x;j++){
			cin >> u;
			edge[u].push_back(i);	
		}
	}
	ans=1e9;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			vis[j]=false;
			boss[j]=0; sum[j]=0;
		}
		q.push(i); s.push(i); vis[i]=true;
		while (!q.empty()){
			now=q.front();
			for (int i=0;i<edge[now].size();i++){
				if (!vis[edge[now][i]]){
					vis[edge[now][i]]=true;
					boss[edge[now][i]]=now;
					q.push(edge[now][i]);
					s.push(edge[now][i]);
				}
			}
			q.pop();
		}
		while (!s.empty()){
			sum[s.top()]++;
			sum[boss[s.top()]]+=sum[s.top()];
			s.pop();
		}
		summm=0;
		for (int j=1;j<=n;j++){
			summm+=sum[j];
		}
		for (int j=1;j<=n;j++){
			if (!vis[j])
			summm=1e9;
			
		}
		ans=min(ans,summm);
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int i=0;i<edge[now].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~

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