Submission #113326

#	Time	Username	Problem	Language	Result	Execution time	Memory
113326		Mahdi_Jfri	Bosses (BOI16_bosses)	C++14	100 / 100	535 ms	768 KiB

bosses

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

#define ll long long
#define pb push_back

const int maxn = 5e3 + 20;

vector<int> adj[maxn];

int d[maxn];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		int k;
		cin >> k;

		while(k--)
		{
			int v;
			cin >> v;
			v--;

			adj[v].pb(i);
		}
	}

	ll res = 1e18;
	for(int src = 0; src < n; src++)
	{
		queue<int> q;

		q.push(src);
		memset(d , 63 , sizeof d);
		d[src] = 0;

		while(!q.empty())
		{
			int v = q.front();
			q.pop();

			for(auto u : adj[v])
				if(d[u] > d[v] + 1)
					d[u] = d[v] + 1 , q.push(u);
		}

		ll sum = 0;
		for(int i = 0; i < n; i++)
			sum += d[i] + 1;

		res = min(res , sum);
	}

	cout << res << endl;
}

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