oj.uz

Submission #79534

# Submission time Handle Problem Language Result Execution time Memory
79534 2018-10-15T01:58:16 Z DrumpfTheGodEmperor Bosses (BOI16_bosses) C++14
100 / 100
 655 ms 944 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1061109567
#define INFLL 4557430888798830399
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
const int N = 5005;
int n, sz[N], hei[N];
vector<int> g[N];
bool used[N];
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 0, n) {
		int k;
		cin >> k;
		while (k--) {
			int x;
			cin >> x;
			x--;
			g[x].pb(i);
		}
	}
	/*
	Salary of person u is equal to the number of nodes inside the subtree
	Fix root as r. At each step just BFS into all possible choices.
	*/
	int res = INF;
	fw (r, 0, n) {
		queue<int> q;
		q.push(r);
		int lft = n;
		memset(used, 0, sizeof used);
		used[r] = 1;
		hei[r] = 0;
		while (!q.empty()) {
			lft--;
			int u = q.front(); q.pop();
			fa (v, g[u]) if (!used[v]) {
				used[v] = 1;
				q.push(v);
				hei[v] = hei[u] + 1;
			}
		}
		int ans = n;
		if (!lft) {
			fw (i, 0, n) ans += hei[i];
			res = min(res, ans);
		}
	}
	cout << res;
	return 0;
}

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 2 ms 532 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 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 2 ms 532 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 764 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 2 ms 532 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 7 ms 764 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 127 ms 872 KB Output is correct
15 Correct 5 ms 872 KB Output is correct
16 Correct 626 ms 932 KB Output is correct
17 Correct 655 ms 944 KB Output is correct
18 Correct 644 ms 944 KB Output is correct