oj.uz

Submission #973834

# Submission time Handle Problem Language Result Execution time Memory
973834 2024-05-02T11:35:52 Z Halym2007 Bosses (BOI16_bosses) C++17
100 / 100
 955 ms 196232 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
#define ll long long
#define pb push_back
#define sz size()

ll n, val[N][N], sub[N], vis[N];
vector <int> v[N], p[N];

void solve (int x, int pr) {
	for (int i : p[x]) {
		if (i == pr) continue;
		solve (i, x);
		sub[x] += sub[i];
	}
	sub[x]++;
}


ll root(int x) {
	queue <int> q;
	for (int i = 1; i <= n; ++i) {
		vis[i] = 0;
		sub[i] = 0;
		p[i].clear();
	}
	q.push(x);
	vis[x] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i : v[x]) {
			if (vis[i]) continue;
			p[x].pb (i);
			vis[i] = 1;
			q.push(i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) return -1;
	}
	solve (x, -1);
	ll ret = 0;
	for (int i = 1; i <= n; ++i) {
		ret += sub[i];
	}
	return ret;
}


int main () {
//	freopen ("input.txt", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int k;
		cin >> k;
		for (int j = 1; j <= k; ++j) {
			cin >> val[i][j];
			v[val[i][j]].pb (i);
		}
	}
	ll jog = 1e18;
	for (int i = 1; i <= n; ++i) {
		ll jj = root (i);
		if (~jj) {
			jog = min (jog, jj);
		}
	}
	cout << jog;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2544 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2544 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4596 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2544 KB Output is correct
4 Correct 1 ms 2660 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4596 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 6 ms 8940 KB Output is correct
13 Correct 4 ms 6920 KB Output is correct
14 Correct 221 ms 195788 KB Output is correct
15 Correct 44 ms 195676 KB Output is correct
16 Correct 570 ms 195920 KB Output is correct
17 Correct 955 ms 196180 KB Output is correct
18 Correct 948 ms 196232 KB Output is correct