oj.uz

Submission #1092513

# Submission time Handle Problem Language Result Execution time Memory
1092513 2024-09-24T09:19:21 Z stdfloat Bosses (BOI16_bosses) C++17
22 / 100
 1500 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

bool tr;

int n, mn = INT_MAX, Sm;

vector<bool> vis;

vector<vector<int>> v, E;

int dfs(int x) {
	int sm = 1;
	vis[x] = true;
	for (auto i : E[x]) {
		if (tr || vis[i]) return tr = true, 0;
		sm += dfs(i);
	}

	Sm += sm;

	return sm;
}

void f(int x, int rt) {
	if (x == rt) f(x + 1, rt);

	if (x == n) {
		Sm = 0;
		tr = false;
		vis.assign(n, false);
		
		dfs(rt);

		if (!tr && !count(vis.begin(), vis.end(), false)) mn = min(mn, Sm);

		return;
	}

	for (auto i : v[x]) {
		E[i].push_back(x);
		
		f(x + 1, rt);

		E[i].pop_back();
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;

	v.assign(n, {});
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		while (k--) {
			int x;
			cin >> x; x--;

			v[i].push_back(x);
		}
	}

	E.assign(n, {});
	for (int i = 0; i < n; i++) {
		f(0, i);
	}

	cout << mn;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Execution timed out 1580 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Execution timed out 1580 ms 348 KB Time limit exceeded
9 Halted 0 ms 0 KB -