oj.uz

Submission #993391

# Submission time Handle Problem Language Result Execution time Memory
993391 2024-06-05T14:35:08 Z vyshniak_n Tax Evasion (LMIO19_mokesciai) C++17
100 / 100
 280 ms 139284 KB 
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

#include <random>
mt19937 rnd(time(0));

const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll K = 7e6 + 100;
const ll LOG = 20;

vector <ll> gr[maxn];
ll up[maxn][LOG], deep[maxn];
void dfs(ll v, ll pr) {
    up[v][0] = pr;
    for (ll i = 1; i < LOG; i++)
        up[v][i] = up[ up[v][i - 1] ][i - 1];

    for (ll to : gr[v]) {
        if (to == pr)
            continue;

        deep[to] = deep[v] + 1;
        dfs(to, v);
    }
}

ll cnt[maxn], id[maxn], ans = inf;
multiset <ll> leaf[maxn];
void calc(ll v, ll pr) {
    id[v] = v;
    for (ll to : gr[v]) {
        if (to == pr)
            continue;

        calc(to, v);
        if (leaf[id[v]].size() < leaf[id[to]].size())
            id[v] = id[to];
    }

    leaf[id[v]].insert(deep[v]);
    for (ll to : gr[v]) {
        if (to == pr || id[v] == id[to])
            continue;
        for (auto it : leaf[id[to]])
            leaf[id[v]].insert(it);
    }

    while (cnt[v]) {
        cnt[v]--;

        auto it = leaf[id[v]].end();
        it--;

        ans = min(ans, *it);
        leaf[id[v]].erase(it);
    }
}

void solve() {
    ll n, m;
    cin >> n >> m;

    for (ll i = 2; i <= n; i++) {
        ll p;
        cin >> p;

        gr[i].pb(p);
        gr[p].pb(i);
    }

    bool ok = 0;

    dfs(1, 1);
    for (ll i = 1; i <= m; i++) {
        ll v, rem;
        cin >> v;

        rem = v;

        if (v == 1)
            ok = 1;

        for (ll j = LOG - 1; j >= 0; j--)
            if (deep[rem] < deep[up[v][j]] * 2)
                v = up[v][j];

        cnt[v]++;
    }

    if (ok)
        return void(cout << 1 << el);

    calc(1, 1);
    cout << ans + 1 << el;
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--) 
        solve();
    return 0;
}
/*
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 6 ms 14644 KB Output is correct
3 Correct 8 ms 16216 KB Output is correct
4 Correct 9 ms 16280 KB Output is correct
5 Correct 7 ms 16448 KB Output is correct
6 Correct 111 ms 87804 KB Output is correct
7 Correct 107 ms 87632 KB Output is correct
8 Correct 7 ms 16472 KB Output is correct
9 Correct 256 ms 84820 KB Output is correct
10 Correct 271 ms 85016 KB Output is correct
11 Correct 167 ms 86352 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 87804 KB Output is correct
2 Correct 107 ms 87632 KB Output is correct
3 Correct 7 ms 16472 KB Output is correct
4 Correct 6 ms 14424 KB Output is correct
5 Correct 7 ms 16188 KB Output is correct
6 Correct 7 ms 16220 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 11 ms 16124 KB Output is correct
9 Correct 11 ms 16988 KB Output is correct
10 Correct 104 ms 82768 KB Output is correct
11 Correct 98 ms 82636 KB Output is correct
12 Correct 168 ms 81592 KB Output is correct
13 Correct 108 ms 82388 KB Output is correct
14 Correct 252 ms 139284 KB Output is correct
15 Correct 164 ms 81600 KB Output is correct
16 Correct 109 ms 82516 KB Output is correct
17 Correct 280 ms 107600 KB Output is correct
18 Correct 104 ms 82772 KB Output is correct
19 Correct 132 ms 75864 KB Output is correct
20 Correct 108 ms 75312 KB Output is correct
21 Correct 106 ms 75236 KB Output is correct
22 Correct 113 ms 75424 KB Output is correct
23 Correct 104 ms 75188 KB Output is correct
24 Correct 99 ms 75092 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 6 ms 14644 KB Output is correct
3 Correct 8 ms 16216 KB Output is correct
4 Correct 9 ms 16280 KB Output is correct
5 Correct 7 ms 16448 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 7 ms 16188 KB Output is correct
8 Correct 7 ms 16220 KB Output is correct
9 Correct 8 ms 16212 KB Output is correct
10 Correct 11 ms 16124 KB Output is correct
11 Correct 11 ms 16988 KB Output is correct
12 Correct 7 ms 16472 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 6 ms 14428 KB Output is correct
15 Correct 6 ms 14576 KB Output is correct
16 Correct 6 ms 14428 KB Output is correct
17 Correct 6 ms 14428 KB Output is correct
18 Correct 11 ms 16188 KB Output is correct
19 Correct 11 ms 16220 KB Output is correct
20 Correct 8 ms 16192 KB Output is correct
21 Correct 9 ms 16728 KB Output is correct
22 Correct 8 ms 16216 KB Output is correct
23 Correct 8 ms 16220 KB Output is correct
24 Correct 11 ms 15964 KB Output is correct
25 Correct 9 ms 15960 KB Output is correct
26 Correct 9 ms 16404 KB Output is correct
27 Correct 9 ms 16216 KB Output is correct
28 Correct 7 ms 15960 KB Output is correct
29 Correct 7 ms 16036 KB Output is correct
30 Correct 9 ms 15960 KB Output is correct
31 Correct 8 ms 15688 KB Output is correct
32 Correct 8 ms 16220 KB Output is correct
33 Correct 9 ms 15708 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14576 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 11 ms 16188 KB Output is correct
7 Correct 11 ms 16220 KB Output is correct
8 Correct 8 ms 16192 KB Output is correct
9 Correct 9 ms 16728 KB Output is correct
10 Correct 8 ms 16216 KB Output is correct
11 Correct 8 ms 16220 KB Output is correct
12 Correct 11 ms 15964 KB Output is correct
13 Correct 9 ms 15960 KB Output is correct
14 Correct 9 ms 16404 KB Output is correct
15 Correct 9 ms 16216 KB Output is correct
16 Correct 7 ms 15960 KB Output is correct
17 Correct 7 ms 16036 KB Output is correct
18 Correct 9 ms 15960 KB Output is correct
19 Correct 8 ms 15688 KB Output is correct
20 Correct 8 ms 16220 KB Output is correct
21 Correct 9 ms 15708 KB Output is correct
22 Correct 8 ms 14424 KB Output is correct
23 Correct 6 ms 14644 KB Output is correct
24 Correct 8 ms 16216 KB Output is correct
25 Correct 9 ms 16280 KB Output is correct
26 Correct 7 ms 16448 KB Output is correct
27 Correct 6 ms 14424 KB Output is correct
28 Correct 7 ms 16188 KB Output is correct
29 Correct 7 ms 16220 KB Output is correct
30 Correct 8 ms 16212 KB Output is correct
31 Correct 11 ms 16124 KB Output is correct
32 Correct 11 ms 16988 KB Output is correct
33 Correct 111 ms 87804 KB Output is correct
34 Correct 107 ms 87632 KB Output is correct
35 Correct 7 ms 16472 KB Output is correct
36 Correct 104 ms 82768 KB Output is correct
37 Correct 98 ms 82636 KB Output is correct
38 Correct 168 ms 81592 KB Output is correct
39 Correct 108 ms 82388 KB Output is correct
40 Correct 252 ms 139284 KB Output is correct
41 Correct 164 ms 81600 KB Output is correct
42 Correct 109 ms 82516 KB Output is correct
43 Correct 280 ms 107600 KB Output is correct
44 Correct 104 ms 82772 KB Output is correct
45 Correct 132 ms 75864 KB Output is correct
46 Correct 108 ms 75312 KB Output is correct
47 Correct 106 ms 75236 KB Output is correct
48 Correct 113 ms 75424 KB Output is correct
49 Correct 104 ms 75188 KB Output is correct
50 Correct 99 ms 75092 KB Output is correct
51 Correct 256 ms 84820 KB Output is correct
52 Correct 271 ms 85016 KB Output is correct
53 Correct 167 ms 86352 KB Output is correct
54 Correct 113 ms 81176 KB Output is correct
55 Correct 105 ms 79188 KB Output is correct
56 Correct 151 ms 80792 KB Output is correct
57 Correct 192 ms 116776 KB Output is correct
58 Correct 177 ms 78404 KB Output is correct
59 Correct 189 ms 77652 KB Output is correct
60 Correct 207 ms 77292 KB Output is correct
61 Correct 264 ms 78804 KB Output is correct
62 Correct 242 ms 95568 KB Output is correct
63 Correct 158 ms 77904 KB Output is correct
64 Correct 147 ms 73392 KB Output is correct
65 Correct 143 ms 73808 KB Output is correct
66 Correct 178 ms 68956 KB Output is correct
67 Correct 152 ms 72016 KB Output is correct
68 Correct 143 ms 74932 KB Output is correct
69 Correct 179 ms 64704 KB Output is correct
70 Correct 126 ms 76076 KB Output is correct
71 Correct 196 ms 101464 KB Output is correct