oj.uz

Submission #33839

# Submission time Handle Problem Language Result Execution time Memory
33839 2017-11-03T02:26:26 Z sinhriv Bosses (BOI16_bosses) C++14
0 / 100
 0 ms 2336 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5050;

int n;
int f[N];
int lst[N];
long long salary[N];
vector < int > gra[N];
vector < pair < int, int > > adj[N];

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int m;
		scanf("%d", &m);

		for(int j = 1; j <= m; ++j){
			int x;
			scanf("%d", &x);
			adj[x].emplace_back(i, 0);
		}
	}

	long long ans = 1e18;

	for(int root = 1; root <= n; ++root){
		memset(f, 0, sizeof f);
		memset(salary, 0, sizeof salary);

		for(int i = 1; i <= n; ++i){
			for(auto &p : adj[i]){
				p.second = 0;
			}
		}

		queue < int > bfs;
		bfs.push(root);
		f[root] = 1;

		int sz = 0;

		while(!bfs.empty()){
			int x = bfs.front();
			bfs.pop();

			lst[++sz] = x;

			for(auto &p : adj[x]){
				if(f[p.first] == 0){
					f[p.first] = 1;
					p.second = 1;
					bfs.push(p.first);
				}
			}
		}

		long long ret = 0;
		
		for(int i = sz; i >= 1; --i){
			int tot = 0;
			for(auto p : adj[lst[i]]){
				if(p.second) tot += salary[p.first];
			}
			salary[lst[i]] = tot + 1;
			ret += salary[lst[i]];
		}
		ans = min(ans, ret);
	}

	cout << ans;

	return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:16:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
bosses.cpp:19:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:22:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
                  ^
bosses.cpp:26:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2336 KB Output is correct
2 Correct 0 ms 2336 KB Output is correct
3 Incorrect 0 ms 2336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2336 KB Output is correct
2 Correct 0 ms 2336 KB Output is correct
3 Incorrect 0 ms 2336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2336 KB Output is correct
2 Correct 0 ms 2336 KB Output is correct
3 Incorrect 0 ms 2336 KB Output isn't correct
4 Halted 0 ms 0 KB -