Submission #895596

#	Time	Username	Problem	Language	Result	Execution time	Memory
895596		d4xn	Tax Evasion (LMIO19_mokesciai)	C++17	32 / 100	83 ms	102600 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], up[N], dep[N], par[N], seg[2][N*4];
vector<int> path, leafs, lvl[N], adj[N];
pair<int, int> sg[N];

void build(int p=1, int l=0, int r=sz-1) {
  if (l == r) {
    seg[0][p] = leafs[l];
    seg[1][p] = l;
    return;
  }

  int mid = (l+r)/2;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);

  seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
  seg[1][p] = (seg[0][p] == seg[0][p*2] ? seg[1][p*2] : seg[1][p*2+1]);
}

void update(int x, int p=1, int l=0, int r=sz-1) {
  if (l == r) {
    seg[0][p]--;
    return;
  }

  int mid = (l+r)/2;
  if (x <= mid) update(x, p*2, l, mid);
  else update(x, p*2+1, mid+1, r);

  seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
  seg[1][p] = (seg[0][p] == seg[0][p*2] ? seg[1][p*2] : seg[1][p*2+1]);
}

pair<int, int> query(int x, int y, int p=1, int l=0, int r=sz-1) {
  if (x <= l && r <= y) {
    return make_pair(seg[0][p], seg[1][p]);
  }

  int mid = (l+r)/2;

  if (y <= mid) {
    return query(x, y, p*2, l, mid);
  }
  else if (x >= mid+1) {
    return query(x, y, p*2+1, mid+1, r);
  }
  else {
    pair<int, int> pr1 = query(x, y, p*2, l, mid);
    pair<int, int> pr2 = query(x, y, p*2+1, mid+1, r);

    if (pr1.first > pr2.first) return pr1;
    else return pr2;
  }
}

pair<int, int> dfs(int x, int u, int d) {
  up[x] = u;
  dep[x] = d;
  lvl[d].push_back(x);

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

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

  if (adj[x].size() == 1 && x) {
    leafs.push_back(dep[x]);
    sg[x] = make_pair(sz, sz);
    sz++;

    path.pop_back();
    return sg[x];
  }

  int mn = inf;
  int mx = -inf;
  for (int& y : adj[x]) {
    if (y == u) continue;
    pair<int, int> child = dfs(y, x, d+1);
    mn = min(mn, child.first);
    mx = max(mx, child.second);
  }

  path.pop_back();
  return sg[x] = make_pair(mn, mx);
}

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);

  build();
  for (int i = n; i >= 1; i--) {
    for (int& x : lvl[i]) {
      while (dol[x] > 0) {
        pair<int, int> pr = query(sg[x].first, sg[x].second);
        dol[x]--;
        ans = min(ans, pr.first);
        update(pr.second);
      }
    }
  }
  cout << ans << "\n";
}

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