Submission #350851

#	Time	Username	Problem	Language	Result	Execution time	Memory
350851		Parsa_PG	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	748 KiB

bosses

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
 
using namespace std;
 
const int maxn = 5e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
vector<int>adj1[maxn] , adj2[maxn] , adj[maxn];
int val[maxn];
bool vis[maxn];
 
int dfs(int v){
	for(auto u : adj1[v]){
		if(vis[u] == 0){
			vis[u] = 1;
			adj[v].pb(u);
		}
	}
	int res = 0;
	for(auto u : adj[v])
		res += dfs(u);
	val[v] = res + 1;
	return res + 1;
}
 
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i ++){
		int k;
		cin >> k;
		for(int j = 0 ; j < k ; j++){
			int u;
			cin >> u;
			u--;
			adj1[u].pb(i);
			adj2[i].pb(u);
		}
	}
	int ans = inf;
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			adj[j].clear();
			vis[j] = 0;
			val[j] = 0;
		}
		vis[i] = 1;
		dfs(i);
		int x = 0;
		for(int j = 0;j < n; j ++){
			x += val[j];
			if(val[j] == 0){
				x = inf;
				break;
			}
		}
		ans = min(ans , x);
	}
	cout << ans << endl;
	return 0;
}

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