Submission #298906

#	Time	Username	Problem	Language	Result	Execution time	Memory
298906		Bruteforceman	Tax Evasion (LMIO19_mokesciai)	C++11	100 / 100	476 ms	57368 KiB

mokesciai

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int logn = 19;
vector <int> g[maxn];
int par[maxn];
int dep[maxn];
int cnt[maxn];
int anc[logn + 1][maxn];
int lift(int x, int depth) {
  for(int i = logn; i >= 0; i--) {
    if(dep[x] - (1 << i) > depth) {
      x = anc[i][x];
    }
  }
  return x;
}
void dfs(int x) {
  for(int i : g[x]) {
    dep[i] = 1 + dep[x];
    dfs(i);
  }
}
int ans = INT_MAX;
void solve(int x, priority_queue <int> &s) {
  s.push(dep[x]);
  for(int i : g[x]) {
    priority_queue <int> t;
    solve(i, t);
    if(t.size() > s.size()) t.swap(s);
    while(not t.empty()) {
      s.push(t.top());
      t.pop();
    }
  }
  for(int j = 0; j < cnt[x]; j++) {
    ans = min(ans, s.top());
    s.pop();
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for(int i = 2; i <= n; i++) {
    cin >> par[i];
    g[par[i]].push_back(i);
    anc[0][i] = par[i];
  }
  for(int i = 1; i <= logn; i++) {
    for(int j = 1; j <= n; j++) {
      anc[i][j] = anc[i - 1][anc[i - 1][j]];
    }
  }
  dep[1] = 1;
  dfs(1);
  vector <int> v;
  for(int i = 1; i <= m; i++) {
    int x;
    cin >> x;
    v.emplace_back(x);
    if(x == 1) {
      cout << 1 << endl;
      exit(0);
    }
  }
  for(auto i : v) {
    int top = (dep[i] + 1) / 2;
    i = lift(i, top);
    cnt[i] += 1;
  }
  priority_queue <int> s;
  solve(1, s);
  cout << ans << endl;
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29