Submission #495026

#	Time	Username	Problem	Language	Result	Execution time	Memory
495026		origami100	Bosses (BOI16_bosses)	C++11	0 / 100	0 ms	300 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n, root = -1;
	cin >> n;
	vector <ll> adjList[n];
	for(ll i = 0; i < n; i++){
		ll k;
		cin >> k;
		if(k == 0){
			root = i;
		}
		for(ll j = 0; j < k; j++){
			ll a;
			cin >> a;
			a--;
			adjList[a].push_back(i);
		}
	}
	if(root == -1){
		ll mi = LONG_LONG_MAX;
		for(ll i = 0; i < n; i++){
			queue <pair <ll, ll> > q;
			stack <pair <ll, ll> > revq;
			q.push(make_pair(i, -1));
			bool vis[n];
			fill(vis, vis + n, false);
			while(!q.empty()){
				ll cur = q.front().first, prev = q.front().second;
				q.pop();
				if(vis[cur]) continue;
				vis[cur] = true;
				if(prev != -1){
					revq.push(make_pair(prev, cur));
				}
				for(ll j = 0; j < adjList[cur].size(); j++){
					q.push(make_pair(adjList[cur][j], cur));
				}
			}
			ll sz[n];
			fill(sz, sz + n, 1);
			while(!revq.empty()){
				ll c = revq.top().second;
				ll p = revq.top().first;
				revq.pop();
				sz[p] += sz[c];
			}
			ll sum = 0;
			for(ll j = 0; j < n; j++){
				sum += sz[j];
			}
			mi = min(mi, sum);
		}
		cout << mi;
	}else{
		queue <pair <ll, ll> > q;
		stack <pair <ll, ll> > revq;
		q.push(make_pair(root, -1));
		bool vis[n];
		fill(vis, vis + n, false);
		while(!q.empty()){
			ll cur = q.front().first, prev = q.front().second;
			q.pop();
			if(vis[cur]) continue;
			vis[cur] = true;
			if(prev != -1){
				revq.push(make_pair(prev, cur));
			}
			for(ll j = 0; j < adjList[cur].size(); j++){
				q.push(make_pair(adjList[cur][j], cur));
			}
		}
		ll sz[n];
		fill(sz, sz + n, 1);
		while(!revq.empty()){
			ll c = revq.top().second;
			ll p = revq.top().first;
			revq.pop();
			sz[p] += sz[c];
		}
		ll sum = 0;
		for(ll j = 0; j < n; j++){
			sum += sz[j];
		}
		cout << sum;
	}
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:37:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(ll j = 0; j < adjList[cur].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
bosses.cpp:70:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(ll j = 0; j < adjList[cur].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

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