Submission #895607

#	Time	Username	Problem	Language	Result	Execution time	Memory
895607		d4xn	Tax Evasion (LMIO19_mokesciai)	C++17	32 / 100	199 ms	61508 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;
    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