Submission #907458

#	Time	Username	Problem	Language	Result	Execution time	Memory
907458		tvladm2009	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	6 ms	19040 KiB

worst_reporter2

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

#define pb push_back
#define int long long
#define ll long long
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>

const int N = 2e5 + 7;
int a[N], h[N], c[N];
vector<int> g[N];
map<int, int> mp[N];

void dfs(int u) {
    for (auto v : g[u]) {
        dfs(v);
        if (mp[v].size() > mp[u].size()) swap(mp[u], mp[v]);
        for (auto it : mp[v]) mp[u][it.first] += it.second;
    }  
    auto it = mp[u].find(h[u]);
    if (it == mp[u].end()) {
        mp[u][h[u]] = c[u];
        it = mp[u].find(a[u]);
    } else {
        mp[u][h[u]] += c[u];
    }
    ll func = c[u];
    while (it != mp[u].begin() && prev(it)->second < func) {
        func -= prev(it)->second;
        mp[u].erase(prev(it));
    }
    if (it != mp[u].begin()) prev(it)->second -= func;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> h[i] >> c[i];
    for (int i = 1; i <= n; i++) if (a[i] != i) g[a[i]].push_back(i);
    dfs(1);
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += c[i];
    for (auto it : mp[1]) sum -= it.second;
    cout << sum << endl;
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21