oj.uz

Submission #695225

# Submission time Handle Problem Language Result Execution time Memory
695225 2023-02-04T19:54:24 Z Cyber_Wolf Bosses (BOI16_bosses) C++17
100 / 100
 747 ms 684 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


const lg N = 5e3+5;

vector<lg> adj[N];
lg vis[N], tmp, dist[N], n;

lg bfs(lg src, lg par = -1)
{
	queue<lg> q;
	q.push(src);
	vis[src] = tmp;
	memset(dist, 0, sizeof(dist));
	lg dis = 1;
	while(q.size())
	{
		lg sz = q.size();
		dis++;
		while(sz--)
		{
			lg u = q.front();
			q.pop();
			for(auto it : adj[u])
			{
				if(vis[it] == tmp)	continue;
				q.push(it);
				vis[it] = tmp;
				dist[it] = dis;
			}	
		}
	}
	lg x = 1; 
	for(int i = 1; i <= n; i++)
	{
		x &= (vis[i] == tmp);
	}
	if(!x)	return 1e18;
	lg ans = 1;
	for(int i = 1; i <= n; i++)	ans += dist[i];
	return ans;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		lg x;
		cin >> x;
		while(x--)
		{
			lg y;
			cin >> y;
			adj[y].push_back(i);
		}
	}
	lg ans = 1e18;
	for(int i = 1; i <= n; i++)
	{
		tmp++;
		lg cur = bfs(i);
		// cout << i << ' ' << cur << '\n';
		ans = min(ans, cur);
	}
	cout << ans << '\n';
	

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 154 ms 596 KB Output is correct
15 Correct 28 ms 620 KB Output is correct
16 Correct 567 ms 684 KB Output is correct
17 Correct 747 ms 668 KB Output is correct
18 Correct 721 ms 664 KB Output is correct