oj.uz

Submission #895604

# Submission time Handle Problem Language Result Execution time Memory
895604 2023-12-30T11:19:52 Z vjudge1 Tax Evasion (LMIO19_mokesciai) C++17
32 / 100
 138 ms 52168 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];
vector<int> path, adj[N];
bitset<N> vis;

void dfs3(int x, set<pair<int, int>>& st) {
  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);
  }
}

set<pair<int, int>> dfs2(int x) {
  set<pair<int, int>> st;
  if (adj[x].size() == 1 && x) {
    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);
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 64 ms 52024 KB Output is correct
7 Correct 55 ms 52160 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 69 ms 52128 KB Output is correct
10 Correct 73 ms 52168 KB Output is correct
11 Correct 73 ms 52112 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 52024 KB Output is correct
2 Correct 55 ms 52160 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 3 ms 8180 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 61 ms 34888 KB Output is correct
11 Correct 50 ms 31312 KB Output is correct
12 Correct 111 ms 20624 KB Output is correct
13 Correct 63 ms 35932 KB Output is correct
14 Correct 82 ms 20052 KB Output is correct
15 Correct 93 ms 20552 KB Output is correct
16 Correct 59 ms 35568 KB Output is correct
17 Correct 138 ms 18956 KB Output is correct
18 Correct 50 ms 36680 KB Output is correct
19 Correct 38 ms 16208 KB Output is correct
20 Correct 38 ms 14164 KB Output is correct
21 Correct 34 ms 14276 KB Output is correct
22 Correct 40 ms 14232 KB Output is correct
23 Correct 51 ms 14228 KB Output is correct
24 Correct 36 ms 13660 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 3 ms 8180 KB Output is correct
9 Correct 3 ms 7772 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 3 ms 7772 KB Output is correct
12 Correct 3 ms 8540 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 1 ms 7260 KB Output is correct
15 Incorrect 1 ms 7260 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Incorrect 1 ms 7260 KB Output isn't correct
4 Halted 0 ms 0 KB -