oj.uz

Submission #594551

# Submission time Handle Problem Language Result Execution time Memory
594551 2022-07-12T16:27:39 Z propransh Bosses (BOI16_bosses) C++14
100 / 100
 748 ms 720 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 532 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 165 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 615 ms 716 KB Output is correct
17 Correct 748 ms 696 KB Output is correct
18 Correct 726 ms 720 KB Output is correct