Submission #254011

#	Time	Username	Problem	Language	Result	Execution time	Memory
254011		Nightlight	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	583 ms	42348 KiB

mokesciai

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

int N, M;
vector<int> adj[200005];
priority_queue<int, vector<int>> pq[200005]; 
int need[200005], can[200005], depth[200005];
bitset<200005> coin;

void DFS(int u, int p) {
  depth[u] = depth[p] + 1;
  for(int v : adj[u]) {
    if(v == p) continue;
    DFS(v, u);
    if(pq[v].size() > pq[u].size()) swap(pq[u], pq[v]);
    need[u] += need[v];
  }
  for(int v : adj[u]) {
    if(v == p) continue;
    while(!pq[v].empty()) pq[u].emplace(pq[v].top()), pq[v].pop();
  }
  if(coin[u]) pq[u].emplace(depth[u] / 2 + (depth[u] & 1));
  while(!pq[u].empty() && pq[u].top() == depth[u]) {
    need[u]++;
    pq[u].pop();
  }
//  cout << u << " " << need[u] << "\n";
}

int l, r, mid, ans;
bool ok;

void check(int u, int p) {
  if(depth[u] >= mid) can[u] = 1;
  else can[u] = 0;
  for(int v : adj[u]) {
    if(v == p) continue;
    check(v, u);
    can[u] += can[v];
  }
  if(can[u] < need[u]) ok = 0;
}

int main() {
  depth[0] = -2;
  ios_base::sync_with_stdio(0);
  cin >> N >> M;
  int u;
  for(int i = 2; i <= N; i++) {
    cin >> u;
    adj[u].push_back(i);
    adj[i].push_back(u);
  }
  for(int i = 1; i <= M; i++) {
    cin >> u;
    coin[u] = 1;
  }
  if(coin[1] == 1) {
    cout << "1\n";
    exit(0);
  }
  DFS(1, 0);
  l = -1, r = N - 2;
  while(l <= r) {
    mid = (l + r) >> 1;
    ok = 1;
    check(1, 0);
    if(ok) {
      ans = mid;
      l = mid + 1;
    }else r = mid - 1;
  }
  cout << ans + 2 << "\n";
  cin >> N;
}

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