Submission #68902

#	Time	Username	Problem	Language	Result	Execution time	Memory
68902		alenam0161	Bosses (BOI16_bosses)	C++17	22 / 100	3 ms	816 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 5007;
vector<int> g[N],g1[N];
bool used[N];
int cur=0;
int dfs(int v,int p=-1){
	int x=0;
	for(int to:g1[v]){
		if(to==p)continue;
		x+=dfs(to,v);
	}
	cur+=x+1;
	return x+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    pair<int,int> mb={-1e9,-1e9};
    for(int i=1;i<=n;++i){
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;++j){
			int p;
			scanf("%d",&p);
			g[p].pb(i);
			mb=max(mb,{(int)g[p].size(),p});
		}
	}
	int ans=1e9;
	for(int i=1;i<=n;++i){
		if(g[i].size()==0)continue;
		if(g[i].size()!=mb.first)continue;
		for(int j=1;j<=n;++j)g1[j].resize(0);
		queue<int> q;
		q.push(i);
		memset(used,0,sizeof(used));
		used[i]=true;
		int hw=1;
		while(!q.empty()){
			int v=q.front();q.pop();
			for(auto to:g[v]){
				if(used[to]==true)continue;
				g1[v].pb(to);
				q.push(to);
				used[to]=true;
				hw++;
			}
		}
		if(hw==n){
			cur=0;
			dfs(i);
			ans=min(ans,cur);
		}
	}
	cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(g[i].size()!=mb.first)continue;
      ~~~~~~~~~~~^~~~~~~~~~
bosses.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bosses.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
   ~~~~~^~~~~~~~~
bosses.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&p);
    ~~~~~^~~~~~~~~

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