oj.uz

Submission #895587

# Submission time Handle Problem Language Result Execution time Memory
895587 2023-12-30T10:38:23 Z d4xn Tax Evasion (LMIO19_mokesciai) C++17
10 / 100
 65 ms 47704 KB 
#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], 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++;

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

  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);
  }
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    x--;
    dol[x]++;
  }
  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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct
4 Correct 6 ms 18264 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 64 ms 47556 KB Output is correct
7 Correct 55 ms 47600 KB Output is correct
8 Correct 4 ms 18264 KB Output is correct
9 Correct 62 ms 47704 KB Output is correct
10 Correct 65 ms 47556 KB Output is correct
11 Correct 56 ms 47556 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 47556 KB Output is correct
2 Correct 55 ms 47600 KB Output is correct
3 Correct 4 ms 18264 KB Output is correct
4 Correct 3 ms 17500 KB Output is correct
5 Incorrect 4 ms 18012 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct
4 Correct 6 ms 18264 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Incorrect 4 ms 18012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct
4 Correct 6 ms 18264 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 3 ms 17500 KB Output is correct
7 Incorrect 4 ms 18012 KB Output isn't correct
8 Halted 0 ms 0 KB -