oj.uz

Submission #81547

# Submission time Handle Problem Language Result Execution time Memory
81547 2018-10-25T09:37:40 Z arman_ferdous Bosses (BOI16_bosses) C++17
100 / 100
 625 ms 1292 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
int n;
vector<int> g[N];

int d[N];
int bfs(int u) {
	queue<int> q; q.push(u);
	memset(d,-1,sizeof d); d[u] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int v : g[u]) if(d[v] == -1) {
			d[v] = d[u] + 1;
			q.push(v);
		}
	} int ret = 0;
	for(int i = 1; i <= n; i++) {
		if(d[i] == -1) return (int)2e9;
		ret += d[i];
	} return ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		int sz, j; scanf("%d", &sz);
		while(sz--) {
			scanf("%d", &j);
			g[j].push_back(i);
		}
	}
	int ans = (int)2e9;
	for(int i = 1; i <= n; i++)
		ans = min(ans, bfs(i));	
	printf("%d\n", ans);
	return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:28:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int sz, j; scanf("%d", &sz);
              ~~~~~^~~~~~~~~~~
bosses.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &j);
    ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 644 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 2 ms 664 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 656 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 2 ms 664 KB Output is correct
12 Correct 7 ms 796 KB Output is correct
13 Correct 6 ms 844 KB Output is correct
14 Correct 126 ms 952 KB Output is correct
15 Correct 7 ms 952 KB Output is correct
16 Correct 586 ms 1172 KB Output is correct
17 Correct 606 ms 1172 KB Output is correct
18 Correct 625 ms 1292 KB Output is correct