Submission #895605

#	Time	Username	Problem	Language	Result	Execution time	Memory
895605		vjudge1	Tax Evasion (LMIO19_mokesciai)	C++17	32 / 100	122 ms	52480 KiB

mokesciai

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

const int N = 2e5+5, inf = INT_MAX;

int n, m, sz, ans, dol[N], up[N], dep[N];
vector<int> path, adj[N];
bitset<N> vis;

void dfs3(int x, set<pair<int, int>>& st, int d) {
  if (d) {
    if (vis[x]) return;
    vis[x] = 1;

    auto it = st.find(make_pair(-dep[x], x));
    if (it != st.end()) st.erase(it);
  }

  for (int& y : adj[x]) {
    if (y == up[x]) continue;
    dfs3(y, st, d+1);
  }
}

set<pair<int, int>> dfs2(int x) {
  set<pair<int, int>> st;
  if (adj[x].size() == 1 && x) {
    st.insert(make_pair(-dep[x], x));
  }

  for (int& y : adj[x]) {
    if (y == up[x]) continue;

    set<pair<int, int>> st2 = dfs2(y);
    if (st2.size() > st.size()) swap(st, st2);
    
    for (pair<int, int> p : st2) {
      st.insert(p);
    }
    st2.clear();
  }

  while (dol[x] > 0) {
    dol[x]--;    
    
    auto it = st.begin();
    int d = it->first;
    int y = it->second;
    st.erase(it);

    ans = min(ans, -d);
    dfs3(up[y], st, 0);
    st.insert(make_pair(d+1, up[y]));
  }
  return st;
}

void dfs(int x, int u, int d) {
  up[x] = u;
  dep[x] = d;

  path.push_back(x);
  if (dol[x] && x) {
    dol[x]--;

    int sz = path.size();
    dol[path[sz - sz/2]]++;
  }

  for (int& y : adj[x]) {
    if (y == u) continue;
    dfs(y, x, d+1);
  }

  path.pop_back();
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  sz = 0;
  ans = inf;
  memset(dol, 0, sizeof(dol));

  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    x--;
    adj[x].push_back(i);
    adj[i].push_back(x);
  }

  bool ok = 1;
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    x--;
    dol[x]++;

    if (!x) ok = 0;
  }
  if (n == 1 || !ok) {
    cout << "1\n";
    return 0;
  }

  dfs(0, 0, 1);
  dfs2(0);

  cout << ans << "\n";
}

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