155942025-02-20 20:19:26BucsMateTevefarmcpp17Wrong answer 38/5090ms5080 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void DFS(vector<vector<int>> &adj, int node, int termeles[], int dp[])
{
    int sum = 0;
    for(int i = 0; i < adj[node].size(); i++){
        DFS(adj, adj[node][i], termeles, dp);
        sum += dp[adj[node][i]];
    }
    dp[node] = max(termeles[node], sum);
}

int BFS(vector<vector<int>> &adj, int termeles[], int dp[], vector<int> &megoldas)
{
    int osszeg = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int currNode = q.front();
        q.pop();
        if(dp[currNode] == termeles[currNode]){
            osszeg += dp[currNode];
            megoldas.push_back(currNode);
            continue;
        }
        for(int i = 0; i < adj[currNode].size(); i++){
            int newNode = adj[currNode][i];
            q.push(newNode);
        }
    }
    return osszeg;
}

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    int termeles[100001];
    for(int i = 1; i <= N; i++){
        cin >> termeles[i];
    }
    for(int i = 2; i <= N; i++){
        int a;
        cin >> a;
        adj[a].push_back(i);
    }

    int dp[100001] = {};
    DFS(adj, 1, termeles, dp);
    vector<int> megoldas;
    cout << BFS(adj, termeles, dp, megoldas) << endl;
    cout << megoldas.size() << endl;
    for(int i = 0; i < megoldas.size(); i++){
        cout << megoldas[i] << " ";
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/01ms564 KiB
2Accepted0/02ms820 KiB
3Accepted4/41ms564 KiB
4Accepted4/41ms568 KiB
5Accepted4/42ms636 KiB
6Accepted4/42ms644 KiB
7Accepted4/443ms3268 KiB
8Accepted6/650ms3780 KiB
9Accepted6/657ms4244 KiB
10Accepted6/671ms4652 KiB
11Wrong answer0/686ms4664 KiB
12Wrong answer0/690ms5080 KiB