oj.uz

Submission #907458

# Submission time Handle Problem Language Result Execution time Memory
907458 2024-01-15T16:02:55 Z tvladm2009 Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 6 ms 19040 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 19040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 19040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 19040 KB Output isn't correct
2 Halted 0 ms 0 KB -