Submission #831468

#	Time	Username	Problem	Language	Result	Execution time	Memory
831468		lovrot	Bosses (BOI16_bosses)	C++17	100 / 100	612 ms	14184 KiB

bosses

#include <cstdio> 
#include <vector> 
#include <algorithm>
#include <cstring>
#include <queue> 

#define PB push_back

using namespace std; 

typedef long long ll;

const int N = 5e5 + 10; 
const ll INF = 1e18; 

int n;
vector<int> G[N]; 

int D[N];
queue<int> Q; 

ll bfs(int s) {
	ll res = 0; 
	memset(D, 0, sizeof(D)); 

	Q.push(s); 
	D[s] = 1;
	
	while(!Q.empty()) {
		int u = Q.front(); 
		Q.pop(); 
	
		res += D[u]; 

		for(int v : G[u]) {
			if(D[v]) continue;
			D[v] = D[u] + 1;
			Q.push(v); 
		}
	}	
	
	for(int u = 1; u <= n; ++u) 
		if(!D[u]) return INF;
	return res;
}

int main() {
	scanf("%d", &n);
	for(int u = 1; u <= n; ++u) {
		int k;
		scanf("%d", &k);
		for(int i = 0; i < k; ++i) {
			int v;
			scanf("%d", &v);
			G[v].PB(u);
		}
	}
	ll ans = INF;
	for(int u = 1; u <= n; ++u) ans = min(ans, bfs(u)); 
	printf("%lld\n", ans);
	return 0; 
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bosses.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d", &k);
      |   ~~~~~^~~~~~~~~~
bosses.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |    scanf("%d", &v);
      |    ~~~~~^~~~~~~~~~

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