Submission #865962

#	Time	Username	Problem	Language	Result	Execution time	Memory
865962		iskhakkutbilim	Bosses (BOI16_bosses)	C++17	100 / 100	561 ms	956 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), parent(n+1, 0), ord;
	dis[root] = 0;
	while(!q.empty()){
		int v =q.front(); q.pop();
		for(int to : g[v]){
			if(dis[to] == -1){
				q.push(to);
				dis[to] = dis[v] + 1;
				parent[to] = v;
				ord.push_back(to);
			}
		}
	}
	for(int i = 1;i <= n; i++){
		if(dis[i] == -1){
			return LLONG_MAX;
		}
		dis[i] = 1;
	}
	sum = 0;
	reverse(all(ord));
	for(int x : ord){
		sum+= dis[x];
		dis[parent[x]]+= dis[x];
	}
	sum+= dis[root];
	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:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

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