Submission #33840

#	Time	Username	Problem	Language	Result	Execution time	Memory
33840		sinhriv	Bosses (BOI16_bosses)	C++14	100 / 100	1253 ms	2468 KiB

bosses

#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);
				}
			}
		}

		if(sz != n) continue;

		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 (stderr)

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: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33