oj.uz

Submission #79887

# Submission time Handle Problem Language Result Execution time Memory
79887 2018-10-17T05:02:00 Z Just_Solve_The_Problem Bosses (BOI16_bosses) C++11
100 / 100
 672 ms 1308 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)5e3 + 7;
const int inf = (int)1e9 + 7;
int n;
ll ans = 1e18;
vector < int > gr[N];
int d[N];

long long solve(int v) {
	ll sum = n;
	queue < int > q;
	for (int i = 1; i <= n; i++) {
		d[i] = inf;
	}
	d[v] = 0;
	q.push(v);
	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (d[to] == inf) {
				d[to] = d[v] + 1;
				q.push(to);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		sum += d[i];
		if (d[i] == inf) {
			return inf;
		}
	}
	return sum;
}
main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int k;
		scanf("%d", &k);
		for (int j = 0; j < k; j++) {
			int as;
			scanf("%d", &as);
			gr[as].push_back(i);
		}
	}                      
	for (int i = 1; i <= n; i++) {
		ans = min(ans, solve(i));
	}
	cout << ans;
}

Compilation message

bosses.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
bosses.cpp: In function 'int main()':
bosses.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~
bosses.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &as);
    ~~~~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 3 ms 708 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 3 ms 708 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 3 ms 708 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 3 ms 708 KB Output is correct
12 Correct 7 ms 772 KB Output is correct
13 Correct 6 ms 804 KB Output is correct
14 Correct 136 ms 964 KB Output is correct
15 Correct 17 ms 1016 KB Output is correct
16 Correct 640 ms 1140 KB Output is correct
17 Correct 672 ms 1256 KB Output is correct
18 Correct 641 ms 1308 KB Output is correct