Submission #106179

#	Time	Username	Problem	Language	Result	Execution time	Memory
106179		dupreez	Bosses (BOI16_bosses)	C++14	100 / 100	671 ms	768 KiB

bosses

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>
#include <climits>
#define mk make_pair
#define pb push_back
#define scanf scanf_s
using namespace std;
typedef long long int ll;
typedef short int ui;
typedef unsigned long long int ull;
const int N = 5010;
int n;
ll ans;
vector<int> g[N];
int main() {
	cin >> n;
	ans = LONG_MAX;
	for (int i = 1; i <= n; i++) {
		int v1; cin >> v1;
		while (v1--) {
			int v2; cin >> v2;
			g[v2].pb(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		ll cv = 0,dpt[N],ct=0;
		memset(dpt, -1, sizeof(dpt));
		dpt[i] = 1;
		queue<int> q; q.push(i);
		while (!q.empty()) {
			int ci = q.front(); q.pop();
			cv += dpt[ci];
			ct++;
			for (int i = 0; i < g[ci].size(); i++) {
				int ni = g[ci][i];
				if (dpt[ni] != -1)continue;
				dpt[ni] = dpt[ci] + 1;
				q.push(ni);
			}
		}
		if(ct==n)
		ans = min(ans, cv);
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

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

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