oj.uz

Submission #422083

# Submission time Handle Problem Language Result Execution time Memory
422083 2021-06-09T17:17:07 Z victoriad Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -