Submission #569511

#	Time	Username	Problem	Language	Result	Execution time	Memory
569511		penguin133	Bosses (BOI16_bosses)	C++14	100 / 100	1449 ms	1184 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
queue<pair<int, int> >q;
int vis[5005], dist[5005];
vector<int>v[5005], ans[5005];
void dfs(int p){
	//cout << p << ' ';
	int sum = 0;
	for(int i=0;i<ans[p].size();i++){
		dfs(ans[p][i]);
		sum += dist[ans[p][i]];
	}
	//cout << ++sum << '\n';
	dist[p] = ++sum;
}
main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		int a;
		cin >> a;
		for(int j=1;j<=a;j++){
			int b;
			cin >> b;
			v[b].push_back(i);
		}
	}
	int cnt = 1e18;
	for(int i=1;i<=n;i++){
		q.push(make_pair(i, 0));
		for(int j=1;j<=n;j++)ans[j].clear();
		for(int j=1;j<=n;j++)vis[j] = 0;
		while(!q.empty()){
			int x = q.front().first, y = q.front().second;
			q.pop();
			if(vis[x])continue;
			vis[x] = true;
			ans[y].push_back(x);
			for(int j=0;j<v[x].size();j++){
				q.push(make_pair(v[x][j], x));
			}
		}
		int c = 0;
		for(int j=1;j<=n;j++)if(!vis[j])c = 1;
		if(c)continue;
		dfs(i);
		int x = 0;
		for(int j=1;j<=n;j++)x += dist[j];
		cnt = min(cnt, x);
		//cout << x << '\n';
		/*
		for(int j=1;j<=n;j++){
			cout << j << " ";
			for(int k=0;k<ans[j].size();k++)cout << ans[j][k] << " ";
			cout << '\n';
		}
		*/
	}
	cout << cnt;
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(long long int)':
bosses.cpp:11:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<ans[p].size();i++){
      |              ~^~~~~~~~~~~~~~
bosses.cpp: At global scope:
bosses.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      | ^~~~
bosses.cpp: In function 'int main()':
bosses.cpp:40:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int j=0;j<v[x].size();j++){
      |                ~^~~~~~~~~~~~

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