Submission #594551

#	Time	Username	Problem	Language	Result	Execution time	Memory
594551		propransh	Bosses (BOI16_bosses)	C++14	100 / 100	748 ms	720 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define boost  ios_base::sync_with_stdio(0);
#define ll long long int
#define pb push_back
#define tc long long int t; cin >> t; while(t--)
#define vpll vector<pair<ll,ll>>
#define MOD 1000000007
vector<ll> adj[5003];
bool vis[5003];
ll level[5003];
ll n;
ll bfs(ll v){
	for(ll i = 0; i < 5003; ++i){
		vis[i] = false;
	}
	vis[v]=true;
	queue <ll> q;
	q.push(v);
	level[v] = 1;
	while(!q.empty()){
		ll p  = q.front();
		//cout<<"here at "<<p<<endl;
		//cout<<p<<" has "<<adj[p].size()<<endl;
		q.pop();
		for(ll i = 0; i < adj[p].size(); i++){
			//cout<<"Trying out "<<adj[p][i]<<endl;
			if(vis[ adj[p][i] ] == false){
				//cout<<"visiting "<<adj[p][i]<<" from "<<p<<endl;
				level[ adj[p][i] ] = level[p]+1;
				q.push( adj[p][i] );
				vis[ adj[p][i] ] = true;
			}
		}
	}
	ll ans= 0 ;

	for(ll i = 1; i <= n; i++){
		if(vis[i] == false){
			return INT_MAX;
		}
		ans += level[i];
		//cout << i << " " << level[i] <<endl;
	}

	return ans;
}
int main(){
	
	boost;
	ll i;
	cin >> n;
	for(i = 0; i < n; i++){
		ll k;
		cin >> k;
		for(ll j=0; j < k; j++){
			ll x;
			cin >> x;
			adj[x].pb(i+1);
		}
	}
	ll m = INT_MAX;
	for(i = 1; i<=n; i++){
		for(ll j = 0; j < 5003; j++){
			vis[i] = false;
			level[i] = 0;
		}
		m = min(m, bfs(i));
	}
	cout << m <<endl;;
	return 0;
} 	

Compilation message (stderr)

bosses.cpp: In function 'long long int bfs(long long int)':
bosses.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(ll i = 0; i < adj[p].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~

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