1329 | 2022. 05. 14 13:10:09 | nkdorka1212 | Tevefarm | cpp11 | Elfogadva 50/50 | 87ms | 31248 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int n;
vector<vector<int>>g;
vector<bool>vis;
vector<int>row;
vector<ll>teve;
void top(int v)
{
vis[v]=true;
for(int x:g[v])
{
if(!vis[x])
{
top(x);
}
}
row.push_back(v);
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
teve.resize(n+1);
vis.resize(n+1,0);
g.resize(n+1);
vector<vector<int>>child(n+1);
vector<int>db(n+1);
vector<ll>maxi(n+1,0);
vector<bool>kifok(n+1,0);
for(int i=1;i<=n;i++)
{
cin>>teve[i];
}
for(int i=2;i<=n;i++)
{
int v;
cin>>v;
g[v].push_back(i);
kifok[v]=true;
}
top(1);
for(int x:row)
{
if(!kifok[x])
{
maxi[x]=teve[x];
child[x].push_back(x);
db[x]=1;
}else
{
ll num=0;
for(int y:g[x])
{
num+=maxi[y];
}
if(teve[x]<num)
{
maxi[x]=num;
for(int y:g[x])
{
child[x].push_back(y);
db[x]+=db[y];
}
}else
{
maxi[x]=teve[x];
child[x].push_back(x);
db[x]=1;
}
}
}
cout<<maxi[1]<<'\n';
cout<<db[1]<<'\n';
queue<int>q;
q.push(1);
while(!q.empty())
{
int v=q.front();
q.pop();
if(child[v][0]==v)
{
cout<<v<<" ";
}else
{
for(int x:g[v])
{
q.push(x);
}
}
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1820 KiB | |||
2 | Elfogadva | 0/0 | 2ms | 2056 KiB | |||
3 | Elfogadva | 4/4 | 2ms | 1876 KiB | |||
4 | Elfogadva | 4/4 | 1ms | 1896 KiB | |||
5 | Elfogadva | 4/4 | 1ms | 1944 KiB | |||
6 | Elfogadva | 4/4 | 1ms | 2144 KiB | |||
7 | Elfogadva | 4/4 | 32ms | 14120 KiB | |||
8 | Elfogadva | 6/6 | 39ms | 17304 KiB | |||
9 | Elfogadva | 6/6 | 48ms | 20444 KiB | |||
10 | Elfogadva | 6/6 | 70ms | 23552 KiB | |||
11 | Elfogadva | 6/6 | 74ms | 27168 KiB | |||
12 | Elfogadva | 6/6 | 87ms | 31248 KiB |