Submission #350847

#	Time	Username	Problem	Language	Result	Execution time	Memory
350847		Parsa_PG	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	620 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] , adj[maxn];
int val[maxn] , n;
bool vis[maxn];

void dfs(int v , int par){
	int res = 0;
	for(auto u : adj[v]){
		if(u == par)
			continue;
		dfs(u , v);
		val[v] += val[u];
	}
	val[v]++;
}

int bfs(int s){
	for(int i =  0 ;i  < n; i++){
		vis[i] =0;
		adj[i].clear();
		val[i] = 0;
	}
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(auto u : adj1[v]){
			if(!vis[u]){
				q.push(u);
				vis[u] = 1;
				adj[v].pb(u);
			}
		}
	}
	dfs(s , -1);
	int res = 0;
	for(int i = 0 ; i < n ; i++){
		res += val[i];
	}
	return res;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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);
		}
	}
	int ans = inf;
	for(int i = 0 ; i < n ; i++){
		ans = min(ans , bfs(i));
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(long long int, long long int)':
bosses.cpp:20:6: warning: unused variable 'res' [-Wunused-variable]
   20 |  int res = 0;
      |      ^~~

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