Submission #68896

#	Time	Username	Problem	Language	Result	Execution time	Memory
68896		Abelyan	Bosses (BOI16_bosses)	C++17	100 / 100	817 ms	1560 KiB

bosses

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <climits>
#include <cstdio>
using namespace std;

typedef long long ll;
struct item {
	int v, dpth;
};

const int N = 5006;
vector<int> g[N];
int col[N];
ll ans;
int n;
queue<item> q;


void bfs(int v,int cl) {
	int k=1;
	q.push({ v,1 });
	col[v] = cl;
	while (!q.empty()) {
		item tv = q.front();
		q.pop();
		ans += (ll)tv.dpth;
		for (auto to : g[tv.v]) {
			if (col[to] == cl) continue;
			//cout << to << endl;
			col[to] = cl;
			//cout << to << endl;
			k++;
			q.push({ to,tv.dpth + 1 });
		}
	}
	if (k != n)ans = LLONG_MAX;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int a;
			cin >> a;
			g[a].push_back(i+1);
		}
	}
	ll mn=LLONG_MAX;
	for (int i = 1; i <= n; i++) {
		ans = 0;
		bfs(i, i);
		//cout << i << " " << ans << endl;
		mn = min(mn, ans);
	}
	if (mn == LLONG_MAX)assert(0);
	cout << mn << endl;
	system("pause");
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:66:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

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