Submission #895615

#	Time	Username	Problem	Language	Result	Execution time	Memory
895615		d4xn	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	260 ms	145848 KiB

mokesciai

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

#define int long long

const int N = 1e6+6, inf = LLONG_MAX;

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

void dfs3(int x, int idx, int d) {
  if (vis[x]) return;
  vis[x] = 1;

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

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

void dfs2(int x) {
  st[x].insert(make_pair(-dep[x], x));

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

    dfs2(y);
    if (st[y].size() > st[x].size()) swap(st[x], st[y]);
    
    for (pair<int, int> p : st[y]) {
      st[x].insert(p);
    }
    st[y].clear();
  }

  //assert(dol2[x] <= st[x].size());
  while (dol2[x] > 0) {
    //cerr << x << " " << dol2[x] << endl;
    dol2[x]--;
    
    auto it = st[x].begin();
    int d = it->first;
    int y = it->second;
    st[x].erase(it);

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

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();
    dol2[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));
  memset(dol2, 0, sizeof(dol2));

  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: 39 / 39
• Subtask 4: 29 / 29