151562025-02-14 10:59:04ercseferencTevefarmcpp17Elfogadva 50/50111ms9344 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct var{vector<int>bem; int kim,ert,val=0; bool van=0,valid=0;};
signed main()
{
    //ifstream f("szamok.txt");
    int n,x; cin>>n; vector<var>a(n+1);
    for(int i=1; i<=n; i++)cin>>a[i].ert;
    bool b[n+1]={};
    for(int i=2; i<=n; i++)
        {cin>>x; a[i].kim=x; b[x]=1; a[x].bem.push_back(i);}
    bool nincs=0;
    vector<int>l1,l2;
    for(int i=1; i<=n; i++)
        {if(!b[i])l1.push_back(i);}
    //cout<<l1.size();
    while(!nincs){
        for(int i=0; i<l1.size(); i++){
            int s=0;
            for(int j=0; j<a[l1[i]].bem.size(); j++)
                {s+=a[a[l1[i]].bem[j]].val;};
            //if(s<a[l1[i]].ert)a[l1[i]].valid=1;
            a[l1[i]].val=max(a[l1[i]].ert,s);
            a[l1[i]].van=0;}
        if(l1.size()==1 && l1[0]==0)nincs=1;
        for(int i=0; i<l1.size(); i++){
            if(a[a[l1[i]].kim].van==0){
                l2.push_back(a[l1[i]].kim);
                a[a[l1[i]].kim].van=1;}}
        if(l2.size()==0)nincs=1;
        l1.clear(); l1=l2; l2.clear();}
    for(int i=1; i<=n; i++){if(a[i].val<=a[i].ert){a[i].valid=1; /*cout<<i<<" ";*/}}
    l1.clear(); l2.clear(); l1.push_back(1); nincs=0; bool ertelme=1;
    vector<int>megold;
    if(a[1].valid){ertelme=0; megold.push_back(1);}
    while(!nincs&&ertelme){
        for(int i=0; i<l1.size(); i++){
            for(int j=0; j<a[l1[i]].bem.size(); j++){
                if(a[a[l1[i]].bem[j]].valid)megold.push_back(a[l1[i]].bem[j]);
                else l2.push_back(a[l1[i]].bem[j]);}}
        if(l2.size()==0)nincs=1;
        l1=l2; l2.clear();}
    cout<<a[1].val<<endl<<megold.size()<<endl;
    for(int i=0; i<megold.size(); i++){cout<<megold[i]<<" ";}//cout<<a[megold[i]].ert<<" ";}
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/02ms316 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/42ms316 KiB
6Elfogadva4/42ms316 KiB
7Elfogadva4/445ms4884 KiB
8Elfogadva6/654ms5624 KiB
9Elfogadva6/668ms6836 KiB
10Elfogadva6/676ms7952 KiB
11Elfogadva6/696ms8368 KiB
12Elfogadva6/6111ms9344 KiB