Submission #771319

#	Time	Username	Problem	Language	Result	Execution time	Memory
771319		pera	Bosses (BOI16_bosses)	C++17	100 / 100	566 ms	6868 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 1;

int n , ans , c , s;
vector<int> g[N] , v(N);

void bfs(int u){
	v[u] = 1;
	queue<pair<int , int>> q;
	q.push({u , 1});
	while(q.size()){
		pair<int , int> x = q.front(); q.pop();
		int p = x.first , k = x.second;
		c += k ++;
		++ s;
		for(int i = 0;i < g[p].size();i ++){
			if(!v[g[p][i]]){
				v[g[p][i]] = 1;
				q.push({g[p][i] , k});
			}
		}
	}
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		int k;cin >> k;
		for(int j = 1;j <= k;j ++){
			int v;cin >> v;
			g[v].push_back(i);
		}
	}
	ans = 1e14;
	for(int boss = 1;boss <= n;boss ++){
		v = vector<int>(n + 1);
		c = s = 0;
		bfs(boss);
		if(s == n) ans = min(ans , c);
	}
	cout << ans << endl;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(long long int)':
bosses.cpp:20: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]
   20 |   for(int i = 0;i < g[p].size();i ++){
      |                 ~~^~~~~~~~~~~~~
bosses.cpp: At global scope:
bosses.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~

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