oj.uz

Submission #895607

# Submission time Handle Problem Language Result Execution time Memory
895607 2023-12-30T11:27:46 Z d4xn Tax Evasion (LMIO19_mokesciai) C++17
32 / 100
 199 ms 61508 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, 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 4 ms 8856 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 91 ms 61316 KB Output is correct
7 Correct 92 ms 61252 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 118 ms 61508 KB Output is correct
10 Correct 119 ms 61380 KB Output is correct
11 Correct 128 ms 61360 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 61316 KB Output is correct
2 Correct 92 ms 61252 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 3 ms 8232 KB Output is correct
6 Correct 3 ms 8280 KB Output is correct
7 Correct 4 ms 7768 KB Output is correct
8 Correct 4 ms 8244 KB Output is correct
9 Correct 4 ms 7772 KB Output is correct
10 Correct 89 ms 42684 KB Output is correct
11 Correct 81 ms 38724 KB Output is correct
12 Correct 119 ms 23492 KB Output is correct
13 Correct 81 ms 42188 KB Output is correct
14 Correct 179 ms 26424 KB Output is correct
15 Correct 121 ms 23640 KB Output is correct
16 Correct 82 ms 42192 KB Output is correct
17 Correct 199 ms 24260 KB Output is correct
18 Correct 101 ms 49736 KB Output is correct
19 Correct 87 ms 26012 KB Output is correct
20 Correct 85 ms 23636 KB Output is correct
21 Correct 86 ms 23380 KB Output is correct
22 Correct 84 ms 23632 KB Output is correct
23 Correct 84 ms 23120 KB Output is correct
24 Correct 80 ms 23124 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 4 ms 8856 KB Output is correct
4 Correct 4 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 3 ms 8232 KB Output is correct
8 Correct 3 ms 8280 KB Output is correct
9 Correct 4 ms 7768 KB Output is correct
10 Correct 4 ms 8244 KB Output is correct
11 Correct 4 ms 7772 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 1 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Incorrect 2 ms 7256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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