oj.uz

Submission #53667

# Submission time Handle Problem Language Result Execution time Memory
53667 2018-06-30T16:59:15 Z wilwxk Bosses (BOI16_bosses) C++17
100 / 100
 969 ms 118424 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=6e3+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 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 596 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 504 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 3 ms 996 KB Output is correct
9 Correct 2 ms 996 KB Output is correct
10 Correct 2 ms 996 KB Output is correct
11 Correct 3 ms 996 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 504 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 3 ms 996 KB Output is correct
9 Correct 2 ms 996 KB Output is correct
10 Correct 2 ms 996 KB Output is correct
11 Correct 3 ms 996 KB Output is correct
12 Correct 9 ms 1636 KB Output is correct
13 Correct 11 ms 1636 KB Output is correct
14 Correct 288 ms 118176 KB Output is correct
15 Correct 125 ms 118304 KB Output is correct
16 Correct 812 ms 118424 KB Output is correct
17 Correct 969 ms 118424 KB Output is correct
18 Correct 885 ms 118424 KB Output is correct