oj.uz

Submission #24888

# Submission time Handle Problem Language Result Execution time Memory
24888 2017-06-16T23:20:15 Z RezwanArefin01 Bosses (BOI16_bosses) C++14
100 / 100
 696 ms 2324 KB 
//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 5555; 
vector<int> adj[maxn];
int vis[maxn], dist[maxn], n; 

ll bfs(int u) {
	queue<int> Q;
	memset(vis, 0, sizeof vis); 
	memset(dist, 0, sizeof dist); 
	vis[u] = 1;
	dist[u] = 1; 
	Q.push(u);
	while(!Q.empty()) {
		int u = Q.front(); Q.pop(); 
		for(int v : adj[u]) if(!vis[v]) {
			Q.push(v); 
			dist[v] = dist[u] + 1; 
			vis[v] = 1;
		}
	} ll sum = 0;
	for(int i=1; i<=n; i++) {
		if(!vis[i]) return 1e9; 	
		sum += dist[i];
	} return sum; 
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	cin>>n; 
	for(int i=1; i<=n; i++) {
		int k; cin>>k ;
		while(k--) {
			int p; cin>>p;
			adj[p].push_back(i); 
		}
	} 
	ll Min = 1e9;
	for(int i=1; i<=n; i++) 
		Min = min(Min, bfs(i));  
	cout<<Min<<endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2192 KB Output is correct
2 Correct 0 ms 2192 KB Output is correct
3 Correct 0 ms 2192 KB Output is correct
4 Correct 0 ms 2192 KB Output is correct
5 Correct 0 ms 2192 KB Output is correct
6 Correct 0 ms 2192 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2192 KB Output is correct
2 Correct 0 ms 2192 KB Output is correct
3 Correct 0 ms 2192 KB Output is correct
4 Correct 0 ms 2192 KB Output is correct
5 Correct 0 ms 2192 KB Output is correct
6 Correct 0 ms 2192 KB Output is correct
7 Correct 0 ms 2192 KB Output is correct
8 Correct 0 ms 2192 KB Output is correct
9 Correct 0 ms 2192 KB Output is correct
10 Correct 0 ms 2192 KB Output is correct
11 Correct 0 ms 2192 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2192 KB Output is correct
2 Correct 0 ms 2192 KB Output is correct
3 Correct 0 ms 2192 KB Output is correct
4 Correct 0 ms 2192 KB Output is correct
5 Correct 0 ms 2192 KB Output is correct
6 Correct 0 ms 2192 KB Output is correct
7 Correct 0 ms 2192 KB Output is correct
8 Correct 0 ms 2192 KB Output is correct
9 Correct 0 ms 2192 KB Output is correct
10 Correct 0 ms 2192 KB Output is correct
11 Correct 0 ms 2192 KB Output is correct
12 Correct 6 ms 2324 KB Output is correct
13 Correct 6 ms 2324 KB Output is correct
14 Correct 153 ms 2324 KB Output is correct
15 Correct 16 ms 2324 KB Output is correct
16 Correct 653 ms 2324 KB Output is correct
17 Correct 693 ms 2324 KB Output is correct
18 Correct 696 ms 2324 KB Output is correct