Submission #424703

#	Time	Username	Problem	Language	Result	Execution time	Memory
424703		blue	Magic Tree (CEOI19_magictree)	C++17	100 / 100	265 ms	20656 KiB

magictree

#include <iostream>
#include <vector>
#include <set>
using namespace std;

/*
O(n*k):

Let dp[u][d] be the maximum amount of juice that can be collected if the edge (u, p[u]) is cut on day d.
Let DP[u][d] = max{d' <= d | dp[u][d']}

dp[u][d] = (d == fruit_day[u]) * fruit_weight[u]
           + sum{v in children[u] | DP[v][d]}

DP[u][d] = max(DP[u][d-1], dp[u][d])


O(n+k)
All the days d where DP[u][d] != DP[u][d-1] are the ripe days of some fruits in the subtree of u.

struct change
{
    int d;
    int changeDP;
}
*/

struct change
{
    int d;
    long long changeDP;
};

bool operator < (change A, change B)
{
    return A.d < B.d;
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> children[n+1];
    for(int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        children[p].push_back(i);
    }

    vector<int> fruit_day(n+1, 1);
    vector<long long> fruit_weight(n+1, 0);
    for(int f = 1; f <= m; f++)
    {
        int v, d, w;
        cin >> v >> d >> w;
        fruit_day[v] = d;
        fruit_weight[v] = w;
    }


    vector<int> subtree(n+1, 1);
    vector<int> maxchild(n+1, -1);

    for(int i = n; i >= 1; i--)
    {
        for(int v: children[i])
        {
            subtree[i] += subtree[v];

            if(maxchild[i] == -1 || subtree[v] > subtree[ maxchild[i] ])
                maxchild[i] = v;
        }
    }


    set<change>* DP[n+1];
    for(int i = 1; i <= n; i++)
    {
        DP[i] = new set<change>;
    }

    for(int u = n; u >= 1; u--)
    {
        // cerr << "u = " << u << '\n';
        if(children[u].size() == 0)
        {
            DP[u]->insert(change{fruit_day[u], +fruit_weight[u]});
        }
        else
        {
            DP[u] = DP[ maxchild[u] ];
            for(int v: children[u])
            {
                if(v == maxchild[u]) continue;
                for(change d: *DP[v])
                {
                    set<change>::iterator X = DP[u]->find(d);
                    if(X == DP[u]->end())
                    {
                        DP[u]->insert(d);
                    }
                    else
                    {
                        change x = *X;
                        DP[u]->erase(x);
                        x.changeDP += d.changeDP;
                        DP[u]->insert(x);
                    }
                }
                DP[v]->clear();
            }

            //Update with fruit(u)
            long long current_fruit_val = fruit_weight[u];
            while(1)
            {
                // cerr << "cfv = " << current_fruit_val << '\n';
                if(current_fruit_val == 0) break;
                set<change>::iterator it = DP[u]->upper_bound(change{fruit_day[u], fruit_weight[u]});

                // if(it == DP[u]->end()) cerr << "it = end\n";
                // else cerr << "it = " << it->d << ' ' << it->changeDP << '\n';

                if(it == DP[u]->end()) break;
                else if(it->changeDP <= current_fruit_val)
                {
                    current_fruit_val -= it->changeDP;
                    DP[u]->erase(it);
                }
                else
                {
                    change X = *it;
                    DP[u]->erase(X);
                    X.changeDP -= current_fruit_val;
                    current_fruit_val = 0;
                    DP[u]->insert(X);
                }
            }

            set<change>::iterator it = DP[u]->find(change{fruit_day[u], +fruit_weight[u]});
            if(it == DP[u]->end())
            {
                DP[u]->insert(change{fruit_day[u], +fruit_weight[u]});
            }
            else
            {
                change x = *it;
                DP[u]->erase(x);
                x.changeDP += +fruit_weight[u];
                DP[u]->insert(x);
            }
        }

        // for(change c:*DP[u]) cerr << c.d << ' ' << c.changeDP << '\n';

    }

    long long res = 0;
    for(change c: *DP[1]) res += c.changeDP;

    cout << res << '\n';
}

• 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