Submission #234878

#	Time	Username	Problem	Language	Result	Execution time	Memory
234878		Atalasion	Bosses (BOI16_bosses)	C++14	100 / 100	1497 ms	1056 KiB

bosses

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 5000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 10000000000010;
const ll LOG = 25;

int n, sm[N];
ll dis[N];
vi G[N], g[N];

void BFS(int v){
	fill(dis + 1, dis + n + 1, INF);
	dis[v] = 0;
	queue<int> q;
	q.push(v);
	while (q.size()){
		int fr = q.front();
		q.pop();
		for (auto u:G[fr]){
			if (dis[u] > dis[fr] + 1){
				dis[u] = dis[fr] + 1;
				g[fr].pb(u);
				q.push(u);
			}
		}
	}
}

void DFS(int v){
	sm[v] = 1;
	for (auto u:g[v]){
		DFS(u);
		sm[v] += sm[u];
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		int k;
		cin >> k;
		for (int j = 0; j < k; j++){
			int x;
			cin >> x;
			G[x].pb(i);
		}
	}
	ll ans = INF;
	for (int i = 1; i <= n; i++){
		memset(sm, 0, sizeof sm);
		for (int j = 1; j <= n; j++) g[j].clear();
		BFS(i);
		bool f = 0;
		for (int j = 1; j <= n; j++) if (dis[j] == INF) f = 1;
		if (f) continue;
//		cout << "YES" << endl;
		DFS(i);
//		cout << "YES2" << endl;
		ll res = 0;
		for (int j = 1; j <= n; j++) res += sm[j];
		ans = min(ans, res);
//		if (sm[i] == 7) cout << i << endl;
	}
	cout << ans;










	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33