Submission #9792745

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, K;
vector<vector<int>> G;
bool desc[310][310], looked[310], chosen[310];
int depth[310], ans[310];

void dfs(int key){
	looked[key]=1;
	desc[key][key]=1;
	for(int i=0; i<G[key].size(); ++i){
		if(!looked[G[key][i]]){
			depth[G[key][i]]=depth[key]+1;
			dfs(G[key][i]);
			for(int j=0; j<=N; ++j){
				desc[key][j]=(desc[key][j]||desc[G[key][i]][j]);
			}
		}
	}
}

int main() {
	cin >> N >> M >> K;
	G.resize(N+1);
	for(int i=1; i<=N; ++i){
		int p;
		cin >> p;
		G[i].emplace_back(p);
		G[p].emplace_back(i);
	}
	depth[0]=0;
	dfs(0);
	int now=0;
	for(int i=0; i<M; ++i){
		for(int j=1; j<=N; ++j){
			if(!chosen[j]){
				vector<int> num;
				for(int k=1; k<=N; ++k){
					if((!chosen[k]) && (!desc[j][k])){
						num.emplace_back(depth[k]);
					}
				}
				if(num.size()<M-i-1) continue;
				sort(num.begin(), num.end());
				int ssum=0, lsum=0;
				for(int k=0; k<M-i-1; ++k){
					ssum += num[k];
					lsum += num[num.size()-1-k];
				}
				if(ssum<=K-now-depth[j] && K-now-depth[j]<=lsum){
					ans[i]=j;
					now += depth[j];
					for(int k=1; k<=N; ++k){
						chosen[k]=(chosen[k]||desc[j][k]);
					}
					break;
				}
			}
		}
		if(ans[i]==0){
			cout << -1 << endl;
			return 0;
		}
	}
	cout << ans[0];
	for(int i=1; i<M; ++i) cout << ' ' << ans[i];
	cout << endl;
	return 0;
}

Submission Info

Judge Result