oj.uz

Submission #74488

# Submission time Handle Problem Language Result Execution time Memory
74488 2018-09-02T12:29:43 Z polyfish Bosses (BOI16_bosses) C++14
100 / 100
 744 ms 1424 KB 
//Pantyhose + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 5002;
const int64_t INF = 1e18;

int n, d[MAX_N];
vector<int> g[MAX_N];

void enter() {
	cin >> n;
	for (int i=1; i<=n; ++i) {
		int k;
		cin >> k;
		while (k--) {
			int u;
			cin >> u;
			g[u].push_back(i);
		}
	}
}

int64_t bfs(int st) {
	queue<int> qu;
	memset(d, 0, sizeof(d));
	d[st] = 1;
	qu.push(st);
	int64_t res = 0;
	int cnt = 0;
	while (qu.size()) {
		int u = qu.front();
		res += d[u];
		++cnt;
		qu.pop();
		for (auto v : g[u]) {
			if (d[v]==0) {
				d[v] = d[u] + 1;
				qu.push(v);
			}
		}
	}
	return cnt!=n ? INF : res;
}

void solve() {
	int64_t res = INF;
	for (int u=1; u<=n; ++u)
		res = min(res, bfs(u));
	cout << res;
}

int main() {
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	solve();
}

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 592 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 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 592 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 800 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 592 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 800 KB Output is correct
12 Correct 6 ms 948 KB Output is correct
13 Correct 5 ms 992 KB Output is correct
14 Correct 128 ms 1072 KB Output is correct
15 Correct 6 ms 1072 KB Output is correct
16 Correct 652 ms 1152 KB Output is correct
17 Correct 744 ms 1216 KB Output is correct
18 Correct 660 ms 1424 KB Output is correct