Submission #256890

#	Time	Username	Problem	Language	Result	Execution time	Memory
256890		anubhavdhar	Bosses (BOI16_bosses)	C++14	100 / 100	719 ms	760 KiB

bosses

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

int N, ans;
vi sub[5010];

inline int set_boss(int s)
{
	bool vis[N+1];
	int dep[N+1], tmp = 0;
	queue<int> Q;

	F0Re(i, N)
		vis[i] = false;

	Q.push(s);
	vis[s] = true;
	dep[s] = 1;

	while(!Q.empty())
	{
		int a = Q.front();
		Q.pop();
		tmp += dep[a];
		for(int b : sub[a])
			if(!vis[b])
			{
				vis[b] = true;
				dep[b] = dep[a] + 1;
				Q.push(b);
			}
	}

	F0Re(i, N)
		if(!vis[i])
			return inf;

	return tmp;
}

signed main()
{

	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/

	ans = inf;
	cin>>N;
	int M, j;
	F0Re(i, N)
	{
		cin>>M;
		while(M--)
			cin>>j, sub[j].pb(i);
	}

	F0Re(i, N)
		ans = min(ans, set_boss(i));

	cout<<ans;
	
	return 0;
}

/*
4
1 4
3 1 3 4
2 1 2
1 3
*/

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