Submission #11169768

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n,m,k,root;
vector<vector<int>> G;
vector<int> d_;
bool used[310];

void dfs(int s,vector<vector<int>> &G_dfs,vector<int> &d_dfs,int l){
  //cout << s << endl;
  d_dfs[s]=l;
  for(int t:G_dfs[s]){
    //cout << t << endl;
    dfs(t,G_dfs,d_dfs,d_dfs[s]+1);
  }
}

bool hantei(int i,int j,int u){
  if(used[j]) return false;
  int l=k-(u+1+d_[j])-(m-i-1);
  //cout << l << endl;
  if(j==root){
    return (i==m-1 && l==0);
  }
  if(i==m-1){
    return l==0;
  }
  vector<vector<int>> G_(n);
  rep(i,n){
    for(int s:G[i]){
      if(s==j) continue;
      G_[i].push_back(s);
    }
  }
  vector<int> d(n,-1);
  dfs(root,G_,d,0);
  int S=0;vector<int> D;
  rep(i,n){
    //cout << d[i] << " ";
    if(d[i]!=-1){
      S+=1;
      D.push_back(d[i]);
    }
  }
  //cout << "" << endl;
  //cout << S << endl;
  sort(D.begin(),D.end());
  int d_sta=0,d_end=0;
  if(S<m-i-1){
    return false;
  }
  rep(p,m-i-1){
    d_sta+=D[p];
    d_end+=D[S-p-1];
  }
  //cout << d_sta << " " << d_end << endl;;
  if(d_sta<=l && l<=d_end){
    G=G_;
    rep(i,n){
      used[i]=(d[i]==-1);
    }
    return true;
  };
  return false;
}

void solve(){
  cin >> n >> m >> k;
  G.resize(n);
  rep(i,n){
    int p;cin >> p;p--;
    if(p==-1)root=i;
    G[p].push_back(i);
  }
  d_.resize(n,-1);
  dfs(root,G,d_,0);
  int l=0;
  vector<int> ans;
  rep(i,m){
    rep(j,n){
      //cout << i << " " << j << " " << l << endl;
      bool f=hantei(i,j,l);
      if(f){
        l+=1+d_[j];
        ans.push_back(j+1);
        break;
      }
      if(j==n-1){
        cout << -1 << endl;
        return;
      }
    }
  }
  rep(i,m){
    cout << ans[i] << " ";
  }
  cout << "" << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Submission Info

Judge Result