1540 2022. 11. 22 18:26:27 TomaSajt Tevefarm cpp14 Elfogadva 50/50 46ms 14452 KiB
#include <bits/stdc++.h>
#define speed ios::sync_with_stdio(0);cin.tie(0)
using namespace std;

vector<vector<int>> g;
vector<int> supply;
vector<bool> marked;
vector<long long> tot;
vector<int> res;

void dfs1(int u) {
    if (g[u].empty()) {
        marked[u] = 1;
        tot[u] = supply[u];
        return;
    }
    tot[u] = 0;
    for (auto v : g[u]) {
        dfs1(v);
        tot[u] += tot[v];
    }
    if (tot[u] < supply[u]) {
        marked[u] = 1;
        tot[u] = supply[u];
    }
}

void dfs2(int u) {
    if (marked[u]) {
        res.push_back(u);
        return;
    }
    for (auto v : g[u]) dfs2(v);
}

int main() {
    speed;
    int n;
    cin >> n;
    g.resize(n + 1);
    marked.resize(n + 1);
    tot.resize(n + 1);
    supply.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> supply[i];
    for (int i = 2; i <= n; i++) {
        int a; cin >> a;
        g[a].push_back(i);
    }
    dfs1(1);
    dfs2(1);
    cout << tot[1] << '\n' << res.size() << '\n';
    for (auto u : res) cout << u << ' ';

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1896 KiB
2 Elfogadva 0/0 3ms 2308 KiB
3 Elfogadva 4/4 2ms 2316 KiB
4 Elfogadva 4/4 2ms 2496 KiB
5 Elfogadva 4/4 2ms 2852 KiB
6 Elfogadva 4/4 2ms 3088 KiB
7 Elfogadva 4/4 21ms 8704 KiB
8 Elfogadva 6/6 26ms 10172 KiB
9 Elfogadva 6/6 30ms 11328 KiB
10 Elfogadva 6/6 34ms 12428 KiB
11 Elfogadva 6/6 41ms 13420 KiB
12 Elfogadva 6/6 46ms 14452 KiB