9318 2024. 02. 20 12:55:07 AGergo Tevefarm cpp17 Hibás válasz 38/50 46ms 18196 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graf;
vector<int> teveCount;
vector<int> Sum;
vector<int> ansList(0);

int value(int ID)
{
    if(Sum[ID] == 0)
    {
        if(graf[ID].size()==0)
        {
            //cout << "sima: " << ID << "-" << teveCount[ID] << endl;
            Sum[ID] = teveCount[ID];
            return teveCount[ID];

        }
        else
        {
            for(int i:graf[ID])
            {
                Sum[ID] += value(i);
                //cout << "a" << i << endl;
            }
            if(Sum[ID] > teveCount[ID])
            {

                teveCount[ID] = Sum[ID];
                //graf[ID].resize(0);
                //cout << "ertek1: " << ID << "-" << teveCount[ID] << ":" << Sum[ID] << endl;
                return(Sum[ID]);
            }
            else
            {
                graf[ID].resize(0);
                //cout << "ertek2: " << ID << "-" << teveCount[ID] << ":" << Sum[ID] << endl;
                Sum[ID] = teveCount[ID];
                return(teveCount[ID]);
            }
        }
    }
    else
    {
        return(Sum[ID]);
    }
}

void addList(int ID)
{
    if(graf[ID].size()==0)
    {
        ansList.resize(ansList.size()+1);
        ansList[ansList.size()-1] = ID;
    }
    else
    {
        for(int i:graf[ID])
        {
            addList(i);
        }
    }
}
int main()
{
    cin.tie(0);
    iostream::sync_with_stdio(0);
    int szam;
    cin >> szam;

    teveCount.resize(szam+1);
    Sum.resize(szam+1,0);


    for(int i=1; i<=szam;i++)
    {
        cin >> teveCount[i];
    }

    graf.resize(szam+1,vector<int>());
    //vector<int> grafto(szam+1);

    int t;
    for(int i=2; i<=szam;i++)
    {
        cin >> t;
        graf[t].resize(graf[t].size()+1);
        graf[t][graf[t].size()-1] = i;

        //grafto[i] = t;
    }

    cout << value(1) << endl;
    addList(1);

    cout << ansList.size() << endl;

    for(int i: ansList)
    {
        cout << i << " ";
    }

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 38/50
1 Elfogadva 0/0 3ms 1824 KiB
2 Elfogadva 0/0 3ms 2392 KiB
3 Elfogadva 4/4 3ms 2364 KiB
4 Elfogadva 4/4 3ms 2372 KiB
5 Elfogadva 4/4 3ms 2716 KiB
6 Elfogadva 4/4 3ms 2844 KiB
7 Elfogadva 4/4 25ms 8484 KiB
8 Elfogadva 6/6 29ms 10212 KiB
9 Elfogadva 6/6 35ms 11872 KiB
10 Elfogadva 6/6 41ms 13960 KiB
11 Hibás válasz 0/6 41ms 15456 KiB
12 Hibás válasz 0/6 46ms 18196 KiB