oj.uz

Submission #350578

# Submission time Handle Problem Language Result Execution time Memory
350578 2021-01-19T06:51:03 Z saniyar_krmi Bosses (BOI16_bosses) C++14
100 / 100
 778 ms 896 KB 
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#define int long long 
#pragma GCC optimize ("Ofast")

//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int maxn = 5000 + 10;
const ll inf = 1e18 + 10;
int n;
vector <int> G[maxn];
bool mark[maxn];
int d[maxn];

ll bfs(int src){
	fill(mark, mark+maxn, 0);
	fill(d, d+maxn, 0);

	queue <int> q;
	q.push(src);
	mark[src] = 1;
	d[src] = 1;

	ll res = 0;
	while(!q.empty()){
		int v = q.front();
		q.pop();

		for(int u: G[v]){
			if(mark[u])
				continue;
			mark[u] = 1;
			d[u] = d[v] + 1;
			q.push(u);
		}
	}

	for(int i=1; i<=n; i++){
		if(d[i] == 0)
			return inf;
		res += d[i];
	}

	return res;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);

	cin >> n;
	int k;
	for(int i=1; i<=n; i++){
		cin >> k;
		int p;
		for(int j=0; j<k; j++){
			cin >> p;
			G[p].push_back(i);
		}
	}

	ll ans = inf;
	for(int i=1; i<=n; i++)
		ans = min(ans, bfs(i));

	cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 5 ms 748 KB Output is correct
14 Correct 122 ms 620 KB Output is correct
15 Correct 11 ms 640 KB Output is correct
16 Correct 556 ms 876 KB Output is correct
17 Correct 750 ms 876 KB Output is correct
18 Correct 778 ms 896 KB Output is correct