Submission #298903

#	Time	Username	Problem	Language	Result	Execution time	Memory
298903		Bruteforceman	Tax Evasion (LMIO19_mokesciai)	C++11	61 / 100	2051 ms	40952 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 vis[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);
  }
}
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);
    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 <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;
    i.second = lift(i.second, top);
    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