Submission #424703

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424703	2021-06-12T09:17:07 Z	blue	Magic Tree (CEOI19_magictree)	C++17	100 / 100	265 ms	20656 KB

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.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	16888 KB	Output is correct
2	Correct	93 ms	16880 KB	Output is correct
3	Correct	265 ms	20656 KB	Output is correct
4	Correct	173 ms	20280 KB	Output is correct
5	Correct	215 ms	20388 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	136 ms	16704 KB	Output is correct
5	Correct	179 ms	20612 KB	Output is correct
6	Correct	149 ms	16708 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	16404 KB	Output is correct
2	Correct	162 ms	15992 KB	Output is correct
3	Correct	168 ms	14992 KB	Output is correct
4	Correct	131 ms	18744 KB	Output is correct
5	Correct	142 ms	15172 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	169 ms	17528 KB	Output is correct
11	Correct	157 ms	17092 KB	Output is correct
12	Correct	147 ms	14948 KB	Output is correct
13	Correct	115 ms	18668 KB	Output is correct
14	Correct	142 ms	15320 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	3376 KB	Output is correct
2	Correct	81 ms	16224 KB	Output is correct
3	Correct	75 ms	16068 KB	Output is correct
4	Correct	80 ms	16244 KB	Output is correct
5	Correct	47 ms	18420 KB	Output is correct
6	Correct	85 ms	14940 KB	Output is correct
7	Correct	66 ms	15084 KB	Output is correct

Subtask #7
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	136 ms	16704 KB	Output is correct
14	Correct	179 ms	20612 KB	Output is correct
15	Correct	149 ms	16708 KB	Output is correct
16	Correct	169 ms	17528 KB	Output is correct
17	Correct	157 ms	17092 KB	Output is correct
18	Correct	147 ms	14948 KB	Output is correct
19	Correct	115 ms	18668 KB	Output is correct
20	Correct	142 ms	15320 KB	Output is correct
21	Correct	34 ms	3948 KB	Output is correct
22	Correct	159 ms	17732 KB	Output is correct
23	Correct	179 ms	17812 KB	Output is correct
24	Correct	219 ms	19164 KB	Output is correct
25	Correct	147 ms	19680 KB	Output is correct
26	Correct	232 ms	18692 KB	Output is correct
27	Correct	167 ms	17448 KB	Output is correct

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	148 ms	16888 KB	Output is correct
11	Correct	93 ms	16880 KB	Output is correct
12	Correct	265 ms	20656 KB	Output is correct
13	Correct	173 ms	20280 KB	Output is correct
14	Correct	215 ms	20388 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	460 KB	Output is correct
18	Correct	136 ms	16704 KB	Output is correct
19	Correct	179 ms	20612 KB	Output is correct
20	Correct	149 ms	16708 KB	Output is correct
21	Correct	183 ms	16404 KB	Output is correct
22	Correct	162 ms	15992 KB	Output is correct
23	Correct	168 ms	14992 KB	Output is correct
24	Correct	131 ms	18744 KB	Output is correct
25	Correct	142 ms	15172 KB	Output is correct
26	Correct	169 ms	17528 KB	Output is correct
27	Correct	157 ms	17092 KB	Output is correct
28	Correct	147 ms	14948 KB	Output is correct
29	Correct	115 ms	18668 KB	Output is correct
30	Correct	142 ms	15320 KB	Output is correct
31	Correct	16 ms	3376 KB	Output is correct
32	Correct	81 ms	16224 KB	Output is correct
33	Correct	75 ms	16068 KB	Output is correct
34	Correct	80 ms	16244 KB	Output is correct
35	Correct	47 ms	18420 KB	Output is correct
36	Correct	85 ms	14940 KB	Output is correct
37	Correct	66 ms	15084 KB	Output is correct
38	Correct	34 ms	3948 KB	Output is correct
39	Correct	159 ms	17732 KB	Output is correct
40	Correct	179 ms	17812 KB	Output is correct
41	Correct	219 ms	19164 KB	Output is correct
42	Correct	147 ms	19680 KB	Output is correct
43	Correct	232 ms	18692 KB	Output is correct
44	Correct	167 ms	17448 KB	Output is correct
45	Correct	44 ms	4256 KB	Output is correct
46	Correct	157 ms	18364 KB	Output is correct
47	Correct	172 ms	18376 KB	Output is correct
48	Correct	249 ms	20388 KB	Output is correct
49	Correct	204 ms	20404 KB	Output is correct
50	Correct	265 ms	19652 KB	Output is correct
51	Correct	226 ms	18324 KB	Output is correct

Submission #424703

Compilation message