Submission #865961

#	Time	Username	Problem	Language	Result	Execution time	Memory
865961		iskhakkutbilim	Bosses (BOI16_bosses)	C++17	67 / 100	1551 ms	1160 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 5000;
int n;
vector<int> g[N+1];
 
 
int sum = 0;
void dfs(int v, int par, vector< vector<int> > &adj, vector<int> &sub){
	sub[v] = 1;
	for(int to : adj[v]){
		if(to == par) continue;
		dfs(to, v, adj, sub);
		sub[v]+= sub[to];	
	}
	sum+= sub[v];
}
 
 
int f(int root){
	queue<int> q; q.push(root);
	vector<int> dis(n+1, -1);
	vector< vector<int> > adj(n+1);
	dis[root] = 0;
	while(!q.empty()){
		int v =q.front(); q.pop();
		for(int to : g[v]){
			if(dis[to] == -1){
				q.push(to);
				adj[v].push_back(to);
				dis[to] = dis[v] + 1;
			}
		}
	}
	for(int i = 1;i <= n; i++){
		if(dis[i] == -1){
			return LLONG_MAX;
		}
	}
	sum = 0;
	dfs(root, root, adj, dis);
	return sum;
}
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n; i++){
		int sz; cin >> sz;
		for(int j = 0;j < sz; j++){
			int x; cin >> x;
			g[x].push_back(i);
		}
	}
	int ans = LLONG_MAX;
	for(int i = 1;i <= n; i++){
		ans = min(ans, f(i));
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

bosses.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

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