Submission #706470

#	Time	Username	Problem	Language	Result	Execution time	Memory
706470		LittleCube	Magic Tree (CEOI19_magictree)	C++14	100 / 100	187 ms	34060 KiB

magictree

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

int n, m, k, p[100005], d[100005], sz[100005];
ll w[100005];
vector<int> E[100005];
map<int, ll> mp[100005];

void dfs(int u)
{
    sz[u] = 1;
    for (int v : E[u])
    {
        dfs(v);
        sz[u] += sz[v];
    }
    sort(E[u].begin(), E[u].end(), [&](int i, int j)
         { return sz[i] > sz[j]; });
    for (int i = 0; i < E[u].size(); i++)
    {
        int v = E[u][i];
        if (i == 0)
            mp[u].swap(mp[v]);
        else
        {
            for(auto [p, val] : mp[v])
                mp[u][p] += val;
            mp[v].clear();
        }
    }
    if(w[u])
    {
        ll r = w[u];
        mp[u][d[u]] += w[u];
        auto iter = mp[u].upper_bound(d[u]);
        while(r > 0 && iter != mp[u].end())
        {
            ll cur = iter->second;
            if(r >= cur)
                iter = mp[u].erase(iter);
            else
                iter->second -= r;
            r -= cur;
        }
    }
}

signed main()
{
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++)
    {
        cin >> p[i];
        E[p[i]].emplace_back(i);
    }
    for (int i = 1; i <= m; i++)
    {
        int v;
        cin >> v;
        cin >> d[v] >> w[v];
    }
    dfs(1);
    ll ans = 0;
    for(auto [p, v] : mp[1])
        ans += v;
    cout << ans << '\n';
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < E[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~
magictree.cpp:27:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |             for(auto [p, val] : mp[v])
      |                      ^
magictree.cpp: In function 'int main()':
magictree.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto [p, v] : mp[1])
      |              ^

• 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