146912025-01-28 08:41:17csdavidTevefarmcpp17Hibás válasz 46/50111ms9012 KiB
#include <iostream>
#include <vector>
#include <queue>
//#include <fstream>
using namespace std;
//#define cin fin
struct node{
    long long dp=0, teve;
    bool bejart=0, kivalaszt=0, megoldas=0;
    vector<long long> gyerek;
    long long szulo, done=0;
};

int main()
{
    //ifstream fin("be2.txt");
    long long n, x, y;
    cin >> n;
    node a[n];
    for(long long i=0; i<n; i++){
        cin >> a[i].teve;
        //a[i].dp=a[i].teve;
    }
    a[0].szulo=-1;
    for(long long i=1; i<n; i++){
        cin >> x;
        a[i].szulo=x-1;
        a[x-1].gyerek.push_back(i);
    }
    queue<long long> q;
    for(long long i=0; i<n; i++){
        if(!a[i].gyerek.size()){
            q.push(i);
            a[i].bejart=1;
        }
    }
    /*for(long long i=0; i<n; i++){
        cout << i << ": ";
        for(auto& it:a[i].gyerek){
            cout << it << ' ';
        }
        cout << '\n';
    }
    cout << "\n\n";*/
    bool jo;
    while(!q.empty()){
            jo=1;
        x=q.front();
        q.pop();
        a[x].dp=0;
        //cout << x << ": ";
        for(auto& it:a[x].gyerek){
            if(a[x].dp==0){
                jo=0;
            }
            a[x].dp+=a[it].dp;
            //cout << '|' << it << ": ";
            //cout << a[it].dp << '|';
        }
       // cout << "\n" << a[x].dp << "\\" << a[x].teve;
        if(x==0){
            continue;
        }
        else if(a[x].teve>a[x].dp){
            a[x].dp=a[x].teve;
            a[x].kivalaszt=1;
            /*if(a[a[x].szulo].bejart==0){
                q.push(a[x].szulo);
                a[a[x].szulo].bejart=1;
            }*/
        }
        /*else if(a[a[x].szulo].bejart==0){
            q.push(a[x].szulo);
            a[a[x].szulo].bejart=1;
        }*/
        if(x!=0){
            a[a[x].szulo].done++;
            if(a[a[x].szulo].done==a[a[x].szulo].gyerek.size()){
                q.push(a[x].szulo);
            }
        }
        //cout << "|||" << a[x].dp << "\n\n";
    }
    /*for(long long i=0; i<n; i++){
            cout << i+1 << ' ' << a[i].dp << '\n';
    }*/
    cout << a[0].dp << '\n';
    q.push(0);
    y=0;
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(auto& it:a[x].gyerek){
            if(a[it].kivalaszt){
                a[it].megoldas=1;
                y++;
            }
            else{
                q.push(it);
            }
        }
    }
    cout << y << '\n';
    for(long long i=0; i<n; i++){
        if(a[i].megoldas){
            cout << i+1 << ' ';
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base46/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/02ms500 KiB
3Hibás válasz0/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/42ms316 KiB
7Elfogadva4/443ms4808 KiB
8Elfogadva6/652ms5688 KiB
9Elfogadva6/663ms6572 KiB
10Elfogadva6/671ms7236 KiB
11Elfogadva6/697ms8244 KiB
12Elfogadva6/6111ms9012 KiB