oj.uz

Submission #486661

# Submission time Handle Problem Language Result Execution time Memory
486661 2021-11-12T09:44:42 Z Koosha_mv Bosses (BOI16_bosses) C++14
100 / 100
 677 ms 836 KB 
#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=10005;

int n,t,ans=N*N,a[N],dist[N];
vector<int> g[N];

void bfs(int source){
	fill(dist,dist+N,N);
	int res=0,cnt=0;
	queue<int> q;
	dist[source]=1;
	q.push(source);
	while(q.size()){
		int u=q.front();
		q.pop();
		cnt++;
		res+=dist[u];
		f(i,0,g[u].size()){
			if(dist[u]+1<dist[g[u][i]]){
				q.push(g[u][i]);
				dist[g[u][i]]=dist[u]+1;
			}
		}
	}
	if(cnt==n){
		minm(ans,res);
	}
}

int main(){
	cin>>n;
	f(i,1,n+1){
		int x,k;
		cin>>k;
		f(j,0,k){
			cin>>x;
			g[x].pb(i);
		}
	}
	f(i,1,n+1){
		bfs(i);
	}	
	cout<<ans;
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   36 |   f(i,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
bosses.cpp:36:3: note: in expansion of macro 'f'
   36 |   f(i,0,g[u].size()){
      |   ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 9 ms 588 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 163 ms 660 KB Output is correct
15 Correct 20 ms 588 KB Output is correct
16 Correct 605 ms 748 KB Output is correct
17 Correct 677 ms 716 KB Output is correct
18 Correct 674 ms 836 KB Output is correct