Submission #532592

#	Time	Username	Problem	Language	Result	Execution time	Memory
532592		GioChkhaidze	Bosses (BOI16_bosses)	C++17	100 / 100	790 ms	700 KiB

bosses

#include <bits/stdc++.h>
 
#define ll long long
#define pb push_back
 
using namespace std;
 
const int N = 5005;
 
vector < ll > g[N];
ll res, ans = 1e18, dep[N];
 
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	ll n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		ll sz;
		cin >> sz;
		for (int j = 1; j <= sz; ++j) {
			ll x;
			cin >> x;
			g[x].pb(i);
		}
	}
	
	queue < ll > q;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			dep[j] = 0;
		} 
 
		res = 0;
		q.push(i);
		dep[i] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			
			res += dep[x];
			for (int j = 0; j < g[x].size(); ++j) {
				int to = g[x][j];
				if (!dep[to]) {
					dep[to] = dep[x] + 1;
					q.push(to);
				}
			}
		}
		
		bool bo = false;
		for (int j = 1; j <= n; ++j) {
			if (!dep[j]) bo = true;
		}
		
		if (!bo) {
			ans = min(ans, res);
		}
		res = 0;
	}
	
	assert(ans != 1e18);
	cout << ans << "\n";
}

Compilation message (stderr)

bosses.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main () {
      | ^~~~
bosses.cpp: In function 'int main()':
bosses.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for (int j = 0; j < g[x].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~

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