Submission #594550

#	Time	Username	Problem	Language	Result	Execution time	Memory
594550		propransh	Bosses (BOI16_bosses)	C++14	0 / 100	3 ms	468 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(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
	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++){
      |                 ~~^~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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