oj.uz

Submission #495026

# Submission time Handle Problem Language Result Execution time Memory
495026 2021-12-18T02:51:38 Z origami100 Bosses (BOI16_bosses) C++11
0 / 100
 0 ms 300 KB 
#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

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

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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