oj.uz

Submission #53665

# Submission time Handle Problem Language Result Execution time Memory
53665 2018-06-30T16:57:09 Z wilwxk Bosses (BOI16_bosses) C++11
67 / 100
 247 ms 98620 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=5e3+5;
const long long INF=1e18;
vector<int> g[MAXN];
int dist[MAXN][MAXN];
queue<int> q;
long long resp;
int n;

void bfs(int ori) {
	q.push(ori); dist[ori][ori]=0;
	while(q.size()) {
		int cur=q.front(); q.pop();
		for(auto viz : g[cur]) {
			if(dist[ori][cur]+1<dist[ori][viz]) {
				dist[ori][viz]=dist[ori][cur]+1;
				q.push(viz);
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		while(a--) {
			int b; scanf("%d", &b);
			g[b].push_back(i);
		}
	}
	
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j]=MAXN;
	for(int i=1; i<=n; i++) bfs(i);
	resp=INF;
	
	//for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) printf("%d ", dist[i][j]); printf("\n"); }
	
	for(int i=1; i<=n; i++) {
		long long cur=0;
		for(int j=1; j<=n; j++) cur+=(dist[i][j]+1);
		if(cur<resp) resp=cur;
	}
	
	printf("%lld\n", resp);
	
}

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:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
bosses.cpp:30:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b; scanf("%d", &b);
           ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 772 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 772 KB Output is correct
7 Correct 3 ms 1048 KB Output is correct
8 Correct 4 ms 1048 KB Output is correct
9 Correct 3 ms 1048 KB Output is correct
10 Correct 3 ms 1100 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 772 KB Output is correct
7 Correct 3 ms 1048 KB Output is correct
8 Correct 4 ms 1048 KB Output is correct
9 Correct 3 ms 1048 KB Output is correct
10 Correct 3 ms 1100 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct
12 Correct 10 ms 1596 KB Output is correct
13 Correct 7 ms 1596 KB Output is correct
14 Incorrect 247 ms 98620 KB Output isn't correct
15 Halted 0 ms 0 KB -