9208 2024. 02. 18 16:18:02 BenedekMarton Tevefarm cpp17 Elfogadva 50/50 100ms 17096 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    long long tevter[n+1];
    for(int i=1; i<=n; i++)
    {
        cin >> tevter[i];
    }
    int osv[n+1];
    osv[1]=0;
    for(int i=2; i<=n; i++)
    {
        cin >> osv[i];
    }
    vector <int> gyv[n+1];
    for(int i=1; i<=n; i++)
    {
        gyv[osv[i]].push_back(i);
    }
    int  keszgyersz[n+1];
    long long osztev[n+1];
    bool kiv[n+1];
    for(int i=1; i<=n; i++)
    {
        kiv[i]=0;
        keszgyersz[i]=0;
    }
    queue <int> q;
    for(int i=1; i<=n; i++)
    {
        if(gyv[i].size()==0)
        {
            q.push(i);
        }
    }
    int x;
    long long gyosz;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        gyosz=0;
        for(int i=0; i<gyv[x].size(); i++)
        {
            gyosz=gyosz+osztev[gyv[x][i]];
        }
        if(gyosz>tevter[x])
        {
            osztev[x]=gyosz;
        }
        else
        {
            osztev[x]=tevter[x];
            kiv[x]=1;
        }
        keszgyersz[osv[x]]++;
        //cout << x << " " << osztev[x] << endl;
        if(x!=0)
        {
            if(keszgyersz[osv[x]]==gyv[osv[x]].size())
            {
                q.push(osv[x]);
            }
        }
    }
    cout << osztev[1] << endl;
    if(kiv[1])
    {
        cout << 1 << endl << 1;
        return 0;
    }
    vector <int> megoldas;
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0; i<gyv[x].size(); i++)
        {
            if(kiv[gyv[x][i]])
            {
                megoldas.push_back(gyv[x][i]);
            }
            else
            {
                q.push(gyv[x][i]);
            }
        }
    }
    cout << megoldas.size() << endl;
    for(int i=0; i<megoldas.size(); i++)
    {
        cout << megoldas[i] << " ";
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1684 KiB
2 Elfogadva 0/0 3ms 2116 KiB
3 Elfogadva 4/4 3ms 2140 KiB
4 Elfogadva 4/4 3ms 2356 KiB
5 Elfogadva 4/4 3ms 2616 KiB
6 Elfogadva 4/4 3ms 2920 KiB
7 Elfogadva 4/4 43ms 9768 KiB
8 Elfogadva 6/6 52ms 11400 KiB
9 Elfogadva 6/6 59ms 13112 KiB
10 Elfogadva 6/6 68ms 14460 KiB
11 Elfogadva 6/6 90ms 15964 KiB
12 Elfogadva 6/6 100ms 17096 KiB