답안 #993391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993391	2024-06-05T14:35:08 Z	vyshniak_n	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	280 ms	139284 KB

mokesciai

//#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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