Submission #477740

#	Time	Username	Problem	Language	Result	Execution time	Memory
477740		Lam_lai_cuoc_doi	Magic Tree (CEOI19_magictree)	C++17	100 / 100	152 ms	17116 KiB

magictree

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;

// https : //codeforces.com/blog/entry/68748
// ki thuat "dao ham": thay vi tinh dp[x], ta tinh dp[x] - dp[x - 1]

constexpr int N = 1e5 + 5;
int n, m, k;
map<int, ll> dp[N];
int d[N], w[N];
vector<int> adj[N];

void Read()
{
    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i)
    {
        int p;
        cin >> p;
        adj[p].emplace_back(i);
    }
    for (int i = 1; i <= m; ++i)
    {
        int v;
        cin >> v;
        cin >> d[v] >> w[v];
    }
}

void Solve()
{
    for (int v = n; v; --v)
    {
        for (auto i : adj[v])
        {
            if (dp[v].size() < dp[i].size())
                swap(dp[i], dp[v]);

            for (auto j : dp[i])
                dp[v][j.first] += j.second;
            dp[i].clear();
        }

        if (d[v])
        {
            ll juice = w[v];
            while (true)
            {
                auto i = dp[v].upper_bound(d[v]);
                if (i == dp[v].end())
                    break;

                if (i->second <= juice)
                {
                    juice -= i->second;
                    dp[v].erase(i);
                }
                else
                {
                    i->second -= juice;
                    break;
                }
            }

            dp[v][d[v]] += w[v];
        }
    }

    ll ans(0);
    for (auto i : dp[1])
        ans += i.second;

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << ":\n";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

magictree.cpp: In function 'void read(T&)':
magictree.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

• 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