oj.uz

Submission #446226

# Submission time Handle Problem Language Result Execution time Memory
446226 2021-07-21T09:49:27 Z mariowong Bosses (BOI16_bosses) C++14
100 / 100
 1340 ms 684 KB 
#include <bits/stdc++.h>

using namespace std;

int n,x,u,ans,boss[5005],sum[5005],now,summm;
bool vis[5005];
vector <int> edge[5005];
queue <int> q;
stack<int> s;
int main(){
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> x;
		for (int j=1;j<=x;j++){
			cin >> u;
			edge[u].push_back(i);	
		}
	}
	ans=1e9;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			vis[j]=false;
			boss[j]=0; sum[j]=0;
		}
		q.push(i); s.push(i); vis[i]=true;
		while (!q.empty()){
			now=q.front();
			for (int i=0;i<edge[now].size();i++){
				if (!vis[edge[now][i]]){
					vis[edge[now][i]]=true;
					boss[edge[now][i]]=now;
					q.push(edge[now][i]);
					s.push(edge[now][i]);
				}
			}
			q.pop();
		}
		while (!s.empty()){
			sum[s.top()]++;
			sum[boss[s.top()]]+=sum[s.top()];
			s.pop();
		}
		summm=0;
		for (int j=1;j<=n;j++){
			summm+=sum[j];
		}
		for (int j=1;j<=n;j++){
			if (!vis[j])
			summm=1e9;
			
		}
		ans=min(ans,summm);
	}
	cout << ans << "\n";
	return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int i=0;i<edge[now].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 420 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 9 ms 432 KB Output is correct
13 Correct 7 ms 460 KB Output is correct
14 Correct 361 ms 588 KB Output is correct
15 Correct 44 ms 580 KB Output is correct
16 Correct 1092 ms 656 KB Output is correct
17 Correct 1327 ms 676 KB Output is correct
18 Correct 1340 ms 684 KB Output is correct