Submission #422083

#	Time	Username	Problem	Language	Result	Execution time	Memory
422083		victoriad	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	204 KiB

bosses

#include <cmath>
#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
using namespace std;

void dfs(vector<vector<int> >&g,vector<int>&s,int n){
	s[n]=1;
	for(int i:g[n]){
		if(s[i]==0){
			dfs(g,s,i);
			s[n]+=s[i];
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k,a;
	cin>>n;
	vector<vector<int> >em(n);
	for(int i=0;i<n;i++){
		cin>>k;
		while(k--){
			cin>>a;
			a--;
			em[a].push_back(i);
		}
	}
	vector<pair<int,int> >si(n);
	for(int i=0;i<n;i++){
		si[i]=make_pair(em[i].size(),i);
	}
	sort(si.rbegin(),si.rend());
	vector<vector<int> >sol(n);
	vector<bool>us(n,false);
	priority_queue<pair<int,int> >cola;
	us[si[0].second]=true;
	cola.push(make_pair(si[0].first,si[0].second));
	while(!cola.empty()){
		int ac=cola.top().second;
		cola.pop();
		for(int i=0;i<em[ac].size();i++){
			if(!us[em[ac][i]]){
				us[em[ac][i]]=true;
				cola.push(make_pair(em[em[ac][i]].size(),em[ac][i]));
				sol[ac].push_back(em[ac][i]);
			}
		}
	}
	vector<int>sa(n,0);
	dfs(sol,sa,si[0].second);
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=sa[i];
	}
	cout<<ans<<"\n";
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i<em[ac].size();i++){
      |               ~^~~~~~~~~~~~~~

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