Submission #1182431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182431		boclobanchat	Bosses (BOI16_bosses)	C++20	100 / 100	431 ms	98648 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
vector<int> ds[MAXN];
int dp[MAXN][MAXN];
queue<int> Q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int m;
		cin>>m;
		while(m--)
		{
			int res;
			cin>>res;
			ds[res].push_back(i);
		}
	}
	long long ans=1e18;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) dp[i][j]=1e9*(i!=j);
		Q.push(i);
		while(!Q.empty())
		{
			int a=Q.front();
			Q.pop();
			for(auto v:ds[a]) if(dp[i][v]>dp[i][a]+1) dp[i][v]=dp[i][a]+1,Q.push(v);
		}
		long long res=0;
		for(int j=1;j<=n;j++) res+=dp[i][j]+1;
		ans=min(ans,res);
	}
	cout<<ans;
}

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