oj.uz

Submission #74485

# Submission time Handle Problem Language Result Execution time Memory
74485 2018-09-02T12:22:53 Z polyfish Bosses (BOI16_bosses) C++14
0 / 100
 2 ms 652 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;
	while (qu.size()) {
		int u = qu.front();
		res += d[u];
		qu.pop();
		for (auto v : g[u]) {
			if (d[v]==0) {
				d[v] = d[u] + 1;
				qu.push(v);
			}
		}
	}
	return 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Incorrect 2 ms 652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Incorrect 2 ms 652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Incorrect 2 ms 652 KB Output isn't correct
4 Halted 0 ms 0 KB -