Submission #388222

#	Time	Username	Problem	Language	Result	Execution time	Memory
388222		negar_a	Bosses (BOI16_bosses)	C++14	100 / 100	1172 ms	836 KiB

bosses

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 5e3 + 5;
int n;
int x[maxn], par[maxn], h[maxn];
int inf = 1e9 + 7, res = 0, ans = inf;
vector <int> adj[maxn];

inline void bfs(int v){
	for(int i = 0; i < n; i ++){
		h[i] = inf;
		x[i] = 1;
		par[i] = -1;
	}
	vector <int> vec;
	queue <int> q;
	q.push(v);
	h[v] = 0;
	while(q.size()){
		int w = q.front();
		q.pop();
		vec.pb(w);
		for(int u : adj[w]){
			if(h[u] > h[w] + 1){
				h[u] = h[w] + 1;
				par[u] = w;
				q.push(u);
			}
		}
	}
	reverse(vec.begin(), vec.end());
	if((int)vec.size() < n){
		res = inf;
	}
	for(int u : vec){
		res += x[u];
		if(par[u] != -1){
			x[par[u]] += x[u];
		}
		if(h[u] >= inf){
			res = inf;
		}
	}
	return;
}

int main(){
	fast_io;
	scanf("%d", &n);
	for(int i = 0; i < n; i ++){
		int t; 
		scanf("%d", &t);
		for(int j = 0; j < t; j ++){
			int x; 
			scanf("%d", &x);
			x --;
			adj[x].pb(i);
		}
	}
	for(int i = 0; i < n; i ++){
		res = 0;
		bfs(i);
		ans = min(ans, res);
	}
	printf("%d", ans);
	
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bosses.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
bosses.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

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