Submission #786052

#	Time	Username	Problem	Language	Result	Execution time	Memory
786052		KN200711	Bosses (BOI16_bosses)	C++14	100 / 100	879 ms	928 KiB

bosses

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

vector<int> ps[5001], edge[5001];
int ck, ans, ct[5001];
bool vis[5001];
int N;

void dfs(int a) {
	ct[a] = 0;
	for(int k=0;k<edge[a].size();k++) {
		dfs(edge[a][k]);
		ct[a] += ct[edge[a][k]];
	}
	ct[a]++;
	ck += ct[a];
}

void solve(int a) {
	ck = 0;
	for(int i=1;i<=N;i++) {
		vis[i] = 0;
		edge[i].clear();
	}
	
	int cs = 1;
	queue<int> S;
	S.push(a);
	vis[a] = 1;
	while(!S.empty()) {
		int b = S.front();
	//	cout<<b<<endl;
		S.pop();
		for(int c=0;c<ps[b].size();c++) {
			if(!vis[ps[b][c]]) {
				vis[ps[b][c]] = 1;
				S.push(ps[b][c]);
				edge[b].push_back(ps[b][c]);
				cs++;
			}
		}
	}
	if(cs != N) return;
	
	dfs(a);
	
//	cout<<a<<" "<<ck<<endl;
	
	ans = min(ans, ck);
}

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int K;
		scanf("%d", &K);
		while(K--) {
			int A;
			scanf("%d", &A);
			ps[A].push_back(i);
		}
	}
	
	ans = 1e9;
	for(int i=1;i<=N;i++) {
		solve(i);
	}
	
	printf("%d\n", ans);
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(int)':
bosses.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int k=0;k<edge[a].size();k++) {
      |              ~^~~~~~~~~~~~~~~
bosses.cpp: In function 'void solve(int)':
bosses.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int c=0;c<ps[b].size();c++) {
      |               ~^~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
bosses.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d", &K);
      |   ~~~~~^~~~~~~~~~
bosses.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &A);
      |    ~~~~~^~~~~~~~~~

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