Submission #569142

#	Time	Username	Problem	Language	Result	Execution time	Memory
569142		beaconmc	Bosses (BOI16_bosses)	C++14	67 / 100	1582 ms	1364 KiB

bosses

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;
ll n;
vector<vector<ll>> bosses;
vector<ll> edges[5001];
vector<ll> newedges[5001];
set<ll> sussy;

ll sum = 0;


int dfs(ll a){
	sussy.insert(a);
	ll sus = 1;
	for (auto&i : newedges[a]){
		sus += dfs(i);
	}
	sum += sus;
	return sus;
}

ll solve(ll a){
	FOR(i,0,5001){
		edges[i] = {};
		newedges[i] = {};
	}
	FOR(i,0,n){
		for (auto&j : bosses[i]){
			edges[j].push_back(i+1);
		}
	}
	vector<bool> visited(n+1);

	queue<ll> q;
	q.push(a);
	visited[a] = 1;

	while (q.size()){
		ll node = q.front();
		q.pop();
		for (auto&i : edges[node]){
			if (!visited[i]){
				q.push(i);
				visited[i] = 1;
				newedges[node].push_back(i);
			}
		}
	}
	sussy.clear();
	sum = 0;
	dfs(a);
	if (sussy.size() != n) return 1000000000;
	return sum;
}



int main(){
	cin >> n;

	FOR(i,0,n){
		ll temp; cin >> temp;
		vector<ll> templis(temp);
		FOR(i,0,temp) cin >> templis[i];
		bosses.push_back(templis);
	}
	ll mini = 1000000000;
	FOR(i,1,n+1){
		mini = min(mini, solve(i));

	}
	cout << mini;
}

Compilation message (stderr)

bosses.cpp: In function 'll solve(ll)':
bosses.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   58 |  if (sussy.size() != n) return 1000000000;
      |      ~~~~~~~~~~~~~^~~~

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