Submission #1170009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170009		antonn	Magic Tree (CEOI19_magictree)	C++20	0 / 100	28 ms	8132 KiB

magictree

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e5 + 7;

int v[N], d[N], w[N], val[N], weight[N], who[N], par[N];
ll dp[N];
vector<int> g[N], ord;

void dfs(int u) {
    for (auto v : g[u]) {
        par[v] = u;
        dfs(v);
    }
    ord.push_back(u);
}

int getfirst(int u) {
    int x = u;
    while (x != 0) {
        if (x != u && val[x] >= val[u]) {
            return x;
        }
        x = par[x];
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m, k; cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> d[i] >> w[i];
        val[v[i]] = d[i];
        weight[v[i]] = w[i];
    }
    dfs(1);
    
    for (int i = 1; i <= n; ++i) {
        if (val[i] == 0) continue;
        who[i] = getfirst(val[i]);
    }
    for (auto u : ord) {
        dp[u] += weight[u];
        
        ll s = 0;
        for (auto v : g[u]) s += dp[v];
        ckmax(dp[u], s);
        dp[who[u]] += dp[u];
    }
    cout << dp[1] << "\n";
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17