Submission #234989

#	Time	Username	Problem	Language	Result	Execution time	Memory
234989		BamiTorabi	Bosses (BOI16_bosses)	C++14	100 / 100	714 ms	760 KiB

bosses

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 5e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int n, dis[maxN];
queue <int> Q;
vector <int> G[maxN];

ll BFS(int st){
	memset(dis, 63, sizeof dis);
	dis[st] = 1;
	Q.push(st);
	while (!Q.empty()){
		int v = Q.front();
		Q.pop();
		for (int u : G[v])
			if (dis[u] > dis[v] + 1){
				dis[u] = dis[v] + 1;
				Q.push(u);
			}
	}
	ll res = 0;
	for (int i = 1; i <= n; i++)
		res += dis[i];
	return res;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		int k; scanf("%d", &k);
		while (k--){
			int u; scanf("%d", &u);
			G[u].push_back(i);
		}
	}
	ll ans = INF;
	for (int i = 1; i <= n; i++)
		ans = min(ans, BFS(i));
	printf("%lld\n", ans);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:59:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
          ~~~~~^~~~~~~~~~
bosses.cpp:61:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int u; scanf("%d", &u);
           ~~~~~^~~~~~~~~~

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