Submission #298897

#	Time	Username	Problem	Language	Result	Execution time	Memory
298897		Bruteforceman	Tax Evasion (LMIO19_mokesciai)	C++11	61 / 100	2060 ms	26620 KiB

mokesciai

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector <int> g[maxn];
int par[maxn];
int dep[maxn];
int vis[maxn];

void dfs(int x) {
  for(int i : g[x]) {
    dep[i] = 1 + dep[x];
    dfs(i);
  }
}
pair <int, int> getFarthest(int x) {
  if(vis[x]) return make_pair(0, x);
  pair <int, int> ans (dep[x], x);
  for(int i : g[x]) {
    ans = max(ans, getFarthest(i)); 
  }
  return ans;
}
int main() {
  int n, m;
  cin >> n >> m;
  for(int i = 2; i <= n; i++) {
    cin >> par[i];
    g[par[i]].push_back(i);
  }
  dep[1] = 1;
  dfs(1);
  vector <pair <int, int>> v;
  for(int i = 1; i <= m; i++) {
    int x;
    cin >> x;
    v.emplace_back(dep[x], x);
    if(x == 1) {
      cout << 1 << endl;
      exit(0);
    }
  }
  for(auto &i : v) {
    int top = (i.first + 1) / 2;
    while(top + 1 < dep[i.second]) {
      i.second = par[i.second];
    }
    i.first = dep[i.second];
  }
  sort(v.begin(), v.end(), greater <pair <int, int>> ());
  int ans = n;
  for(auto &i : v) {
    auto j = getFarthest(i.second);
    vis[j.second] = true;
    ans = min(ans, j.first);
  }
  cout << ans << endl;
  return 0;
}

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