Submission #1264812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264812		thaibeo123	Magic Tree (CEOI19_magictree)	C++20	100 / 100	87 ms	29252 KiB

magictree

#include <bits/stdc++.h>
using namespace std;

#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const int N = 1e5 + 5;

int n, m, k;
int d[N], w[N];
vector<int> g[N];

map<int, ll> dfs(int u) {
    map<int, ll> res;
    for (int v : g[u]) {
        map<int, ll> cur = dfs(v);
        if (res.size() < cur.size()) swap(res, cur);
        for (auto x : cur) {
            res[x.fi] += x.se;
        }
    }
    if (d[u]) {
        res[d[u]] += w[u];
        auto it = res.upper_bound(d[u]);
        while (it != res.end()) {
            if (it->se > w[u]) {
                it->se -= w[u];
                break;
            }
            else {
                w[u] -= it->se;
                it = res.erase(it);
            }
        }
    }
    return res;
}

void input() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        g[x].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x >> d[x] >> w[x];
    }
}

void solve() {
    map<int, ll> res = dfs(1);
    ll ans = 0;
    for (auto x : res) {
        ans += x.se;
    }
    cout << ans;
}

signed main() {
    if (fopen(NAME".INP", "r")) {
        freopen(NAME".INP", "r", stdin);
        freopen(NAME".OUT", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    input();
    solve();

    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(NAME".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(NAME".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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