oj.uz

Submission #388222

# Submission time Handle Problem Language Result Execution time Memory
388222 2021-04-10T15:07:29 Z negar_a Bosses (BOI16_bosses) C++14
100 / 100
 1172 ms 836 KB 
//!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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 440 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 6 ms 564 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 270 ms 656 KB Output is correct
15 Correct 41 ms 584 KB Output is correct
16 Correct 865 ms 740 KB Output is correct
17 Correct 1172 ms 836 KB Output is correct
18 Correct 1161 ms 836 KB Output is correct