Submission #1179616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179616		nguyn	Bosses (BOI16_bosses)	C++20	100 / 100	416 ms	820 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 5e3 + 5;

int n;
vector<int> g[N];
int res = 1e9;

void bfs(int s) {
	vector<int> d(n + 3);
	vector<int> vis(n + 3); 
	for (int i = 1; i <= n; i++) {
		d[i] = 1e9;
	}
	d[s] = 1;
	queue<int> q;  
	q.push(s);
	while(!q.empty()) {
		int u = q.front(); 
		q.pop();

		if (vis[u]) continue;
		vis[u] = 1; 

		for (int v : g[u]) {
			if (d[u] + 1 < d[v]) {
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	int tmp = 0;
	// cout << s << '\n';
	for (int i = 1; i <= n; i++) {
		// cout << d[i] << ' ';
		tmp += d[i]; 
	} //cout << '\n';
	// if (tmp > 1e9) return;
	res = min(res, tmp);
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	int sz; cin >> sz;
    	for (int j = 1; j <= sz; j++) {
    		int x; cin >> x;
    		g[x].pb(i); 
    	}
    }
   	for (int i = 1; i <= n; i++) {
   		bfs(i); 
   	}
   	cout << res;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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