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 |