oj.uz

Submission #66420

# Submission time Handle Problem Language Result Execution time Memory
66420 2018-08-10T13:24:51 Z Adhyyan1252 Bosses (BOI16_bosses) C++11
100 / 100
 874 ms 952 KB 
#include<bits/stdc++.h>

using namespace std;

int main(){
	int n; cin>>n;
	vector<vector<int> > g(n);
	for(int i = 0; i < n; i++){
		int k; cin>>k;
		for(int j = 0; j < k; j++){
			int temp; cin>>temp;
			g[temp-1].push_back(i);
		}
	}
	long long best = LONG_LONG_MAX;
	for(int root = 0; root < n; root++){
		queue<pair<int, int> > q;
		vector<bool> done(n, false);
		done[root] = true;
		q.push({root, 1});
		long long ans = 0;
		int count = 0;
		while(!q.empty()){
			count++;
			auto top = q.front(); q.pop();
			ans += top.second;
			for(int i = 0; i < g[top.first].size(); i++){
				if(done[g[top.first][i]]) continue;
				q.push({g[top.first][i], top.second+1});
				done[g[top.first][i]] = true;
			}
		}
		//cout<<"R: "<<root<<" "<<count<<" "<<ans<<endl;
		if(count == n)
			best = min(best, ans);
	}
	cout<<best<<endl;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < g[top.first].size(); i++){
                   ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 12 ms 588 KB Output is correct
13 Correct 15 ms 588 KB Output is correct
14 Correct 194 ms 804 KB Output is correct
15 Correct 8 ms 808 KB Output is correct
16 Correct 736 ms 824 KB Output is correct
17 Correct 866 ms 952 KB Output is correct
18 Correct 874 ms 952 KB Output is correct