146692025-01-27 09:51:30csdavidTevefarmcpp17Hibás válasz 4/5097ms6712 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct node{
    int dp, teve;
    bool bejart=0, kivalaszt=0, megoldas=0;
    vector<int> gyerek;
    int szulo;
};

int main()
{
    int n, x, y;
    cin >> n;
    node a[n];
    for(int i=0; i<n; i++){
        cin >> a[i].teve;
    }
    a[0].szulo=-1;
    for(int i=1; i<n; i++){
        cin >> x;
        a[i].szulo=x-1;
        a[x-1].gyerek.push_back(i);
    }
    queue<int> q;
    for(int i=0; i<n; i++){
        if(!a[i].gyerek.size()){
            q.push(i);
            a[i].bejart=1;
        }
    }
    while(!q.empty()){
        x=q.front();
        q.pop();
        a[x].dp=0;
        for(auto& it:a[x].gyerek){
            a[x].dp+=a[it].dp;
        }
        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;
        }
    }
    cout << a[0].dp << '\n';
    q.push(0);
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(auto& it:a[x].gyerek){
            if(a[it].kivalaszt){
                a[it].megoldas=1;
            }
            else{
                q.push(it);
            }
        }
    }
    for(int i=0; i<n; i++){
        if(a[i].megoldas){
            cout << i+1 << ' ';
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/50
1Hibás válasz0/01ms316 KiB
2Hibás válasz0/02ms508 KiB
3Hibás válasz0/41ms316 KiB
4Részben helyes2/41ms316 KiB
5Részben helyes2/41ms316 KiB
6Hibás válasz0/42ms316 KiB
7Hibás válasz0/441ms3636 KiB
8Hibás válasz0/650ms4404 KiB
9Hibás válasz0/656ms4916 KiB
10Hibás válasz0/667ms5696 KiB
11Hibás válasz0/686ms6156 KiB
12Hibás válasz0/697ms6712 KiB