oj.uz

Submission #895596

# Submission time Handle Problem Language Result Execution time Memory
895596 2023-12-30T10:49:28 Z d4xn Tax Evasion (LMIO19_mokesciai) C++17
32 / 100
 83 ms 102600 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 64488 KB Output is correct
2 Correct 13 ms 64348 KB Output is correct
3 Correct 14 ms 65116 KB Output is correct
4 Correct 14 ms 65204 KB Output is correct
5 Correct 15 ms 65116 KB Output is correct
6 Correct 63 ms 102596 KB Output is correct
7 Correct 64 ms 102600 KB Output is correct
8 Correct 14 ms 65160 KB Output is correct
9 Correct 75 ms 102452 KB Output is correct
10 Correct 74 ms 102592 KB Output is correct
11 Correct 65 ms 102592 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 102596 KB Output is correct
2 Correct 64 ms 102600 KB Output is correct
3 Correct 14 ms 65160 KB Output is correct
4 Correct 13 ms 64344 KB Output is correct
5 Correct 13 ms 64856 KB Output is correct
6 Correct 13 ms 64856 KB Output is correct
7 Correct 14 ms 64856 KB Output is correct
8 Correct 14 ms 65012 KB Output is correct
9 Correct 14 ms 64868 KB Output is correct
10 Correct 55 ms 95296 KB Output is correct
11 Correct 52 ms 95292 KB Output is correct
12 Correct 71 ms 91904 KB Output is correct
13 Correct 63 ms 94644 KB Output is correct
14 Correct 48 ms 87224 KB Output is correct
15 Correct 74 ms 91800 KB Output is correct
16 Correct 62 ms 94664 KB Output is correct
17 Correct 83 ms 87580 KB Output is correct
18 Correct 62 ms 93132 KB Output is correct
19 Correct 53 ms 83024 KB Output is correct
20 Correct 52 ms 81328 KB Output is correct
21 Correct 51 ms 81232 KB Output is correct
22 Correct 51 ms 81232 KB Output is correct
23 Correct 49 ms 81464 KB Output is correct
24 Correct 48 ms 80724 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 64488 KB Output is correct
2 Correct 13 ms 64348 KB Output is correct
3 Correct 14 ms 65116 KB Output is correct
4 Correct 14 ms 65204 KB Output is correct
5 Correct 15 ms 65116 KB Output is correct
6 Correct 13 ms 64344 KB Output is correct
7 Correct 13 ms 64856 KB Output is correct
8 Correct 13 ms 64856 KB Output is correct
9 Correct 14 ms 64856 KB Output is correct
10 Correct 14 ms 65012 KB Output is correct
11 Correct 14 ms 64868 KB Output is correct
12 Correct 14 ms 65160 KB Output is correct
13 Correct 13 ms 64344 KB Output is correct
14 Correct 12 ms 64348 KB Output is correct
15 Correct 12 ms 64344 KB Output is correct
16 Correct 13 ms 64344 KB Output is correct
17 Correct 12 ms 64248 KB Output is correct
18 Correct 14 ms 64860 KB Output is correct
19 Correct 14 ms 64996 KB Output is correct
20 Correct 14 ms 65116 KB Output is correct
21 Correct 14 ms 64860 KB Output is correct
22 Correct 14 ms 64708 KB Output is correct
23 Incorrect 14 ms 64856 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 64344 KB Output is correct
2 Correct 12 ms 64348 KB Output is correct
3 Correct 12 ms 64344 KB Output is correct
4 Correct 13 ms 64344 KB Output is correct
5 Correct 12 ms 64248 KB Output is correct
6 Correct 14 ms 64860 KB Output is correct
7 Correct 14 ms 64996 KB Output is correct
8 Correct 14 ms 65116 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 14 ms 64708 KB Output is correct
11 Incorrect 14 ms 64856 KB Output isn't correct
12 Halted 0 ms 0 KB -