233 2021. 03. 05 10:50:27 mraron Tevefarm cpp14 Elfogadva 50/50 61ms 21272 KiB
#include <bits/stdc++.h>

using namespace std;

int n;
long long t[100000];
vector<int> g[100000];
bool choose[100000], visited[100000];
vector<int> cities;

long long calc(int p)
{
    visited[p] = true;
    long long sum = 0;
    for (int q : g[p])
    {
        if (!visited[q])
        {
            sum += calc(q);
        }
    }
    if (t[p] < sum)
    {
        return sum;
    }
    else
    {
        choose[p] = true;
        return t[p];
    }
}

void get_cities(int p)
{
    visited[p] = true;
    if (choose[p])
    {
        cities.push_back(p);
    }
    else
    {
        for (int q : g[p])
        {
            if (!visited[q])
            {
                get_cities(q);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> t[i];
    }

    for (int i = 1; i < n; ++i)
    {
        int p;
        cin >> p;
        --p;
        g[i].push_back(p);
        g[p].push_back(i);
    }

    cout << calc(0) << '\n';

    fill(visited, visited + n, false);
    get_cities(0);

    cout << cities.size() << '\n';
    for (int x : cities)
    {
        cout << x + 1 << ' ';
    }
    cout << '\n';

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 4ms 6592 KiB
2 Elfogadva 0/0 3ms 6704 KiB
3 Elfogadva 4/4 3ms 6588 KiB
4 Elfogadva 4/4 3ms 6600 KiB
5 Elfogadva 4/4 4ms 6624 KiB
6 Elfogadva 4/4 4ms 6788 KiB
7 Elfogadva 4/4 26ms 11800 KiB
8 Elfogadva 6/6 32ms 13328 KiB
9 Elfogadva 6/6 37ms 15032 KiB
10 Elfogadva 6/6 43ms 16640 KiB
11 Elfogadva 6/6 57ms 18948 KiB
12 Elfogadva 6/6 61ms 21272 KiB