10012022-02-21 08:34:28kidesoSzállításcpp14Elfogadva 40/4010ms4680 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define pii pair<int,int>
#define X first
#define Y second
using namespace std;

vector<vector<int> > x;
vector<int> m, apa, kov, res;
vector<bool> kell;
vector<pii> s;
int N, ans = -1, K;

void kiir() {
	for (int i = 1; i <= N; ++i)
		cout << m[i] << ' ' << kell[i] << ' ' << kov[i] << '\n';

	for (auto e : s)
		cout << e.X << ' ' << e.Y << '\n';
}

void mely(int csp){
	
	if (x[csp].empty()) {
		kell[csp] = true;
		kov[csp] = 0;
		m[csp] = 1;
		return;
	}

	int p = x[csp][0];

	for (auto e : x[csp]) {
		mely(e);
		if (m[p] < m[e]) p = e;
	}

	kell[p] = false;
	kell[csp] = true;
	m[csp] = m[p] + 1;
	kov[csp] = p;
}

bool r(const pii& a, const pii& b) { return a.X > b.X; }

int main()
{
	cin >> N >> K;
	x.resize(N + 1), m.resize(N + 1), apa.resize(N + 1);
	kell.resize(N + 1, false), kov.resize(N + 1, 0);

	for (int i = 1; i <= N; ++i) {
		cin >> apa[i];
		if (apa[i] != 0) x[apa[i]].push_back(i);
	}

	mely(1);
	for (int i = 1; i <= N; ++i)
		if (kell[i]) s.push_back({ m[i],i });

	//kiir();

	sort(s.begin(), s.end(), r);
	
	if (K > s.size()) K = s.size();

	for (int i = 0; i < K; ++i) {
		int p = s[i].Y;
		ans += m[p];
		while (kov[p]) p = kov[p];
		res.push_back(p);
	}

	cout << ans << '\n';
	for (auto e : res) cout << e << ' ';

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/02ms1740 KiB
2Elfogadva0/03ms2476 KiB
3Elfogadva2/21ms1864 KiB
4Elfogadva2/21ms1892 KiB
5Elfogadva2/21ms1900 KiB
6Elfogadva2/21ms1916 KiB
7Elfogadva2/21ms1924 KiB
8Elfogadva2/21ms1932 KiB
9Elfogadva2/21ms1944 KiB
10Elfogadva2/21ms1948 KiB
11Elfogadva2/22ms2212 KiB
12Elfogadva2/23ms2280 KiB
13Elfogadva2/24ms2500 KiB
14Elfogadva2/24ms2696 KiB
15Elfogadva2/24ms2780 KiB
16Elfogadva2/24ms2876 KiB
17Elfogadva3/34ms3120 KiB
18Elfogadva3/36ms3340 KiB
19Elfogadva3/310ms4580 KiB
20Elfogadva3/310ms4680 KiB