Submission #254132

#	Time	Username	Problem	Language	Result	Execution time	Memory
254132		rama_pang	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	303 ms	70136 KiB

mokesciai

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 200005;
const int INF = 1e8;

int N, M;
int A[MAXN];
vector<int> adj[MAXN];

int depth[MAXN];
int lift[MAXN][20];

void DfsInit(int u) {
  for (int j = 1; j < 20; j++) {
    lift[u][j] = lift[lift[u][j - 1]][j - 1];
  }
  for (auto v : adj[u]) {
    lift[v][0] = u;
    depth[v] = depth[u] + 1;
    DfsInit(v);
  }
}

int dp[MAXN];
multiset<int> leaf[MAXN];

void Dfs(int u) {
  dp[u] = INF;
  leaf[u].emplace(depth[u]);
  for (auto v : adj[u]) {
    Dfs(v);
    if (leaf[u].size() < leaf[v].size()) swap(leaf[u], leaf[v]);
    for (auto i : leaf[v]) leaf[u].emplace(i);
    leaf[v].clear();
    dp[u] = min(dp[u], dp[v]);
  }
  while (A[u] > 0) {
    A[u]--;
    auto it = prev(end(leaf[u]));
    dp[u] = min(dp[u], *it);
    leaf[u].erase(it);
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  for (int i = 2; i <= N; i++) {
    int p;
    cin >> p;
    adj[p].emplace_back(i);
  }
  for (int i = 0; i < M; i++) {
    int x;
    cin >> x;
    A[x]++;
  }
  if (A[1]) {
    cout << 1 << "\n";
    return 0;
  }

  DfsInit(1);
  for (int i = 1; i <= N; i++) {
    if (A[i]) {
      int u = i;
      for (int j = 19; j >= 0; j--) {
        if (lift[u][j] != 0 && depth[lift[u][j]] > depth[i] - depth[lift[u][j]]) {
          u = lift[u][j];
        }
      }
      A[u]++;
      A[i]--;
    }
  }

  Dfs(1);
  cout << 1 + dp[1] << "\n";
  return 0;
}

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