Submission #703486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703486	2023-02-27T13:43:52 Z	Cyanmond	Magic Tree (CEOI19_magictree)	C++17	47 / 100	2000 ms	787112 KB

magictree

#include <bits/stdc++.h>

using i64 = long long;
struct Vertice {
    bool exFruit;
    int day;
    i64 weight;
};

int main() {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::vector<int> P(N);
    std::vector<std::vector<int>> tree(N);
    for (int i = 1; i < N; ++i) {
        std::cin >> P[i];
        --P[i];
        tree[P[i]].push_back(i);
    }
    std::vector<int> U(M), D(M);
    std::vector<i64> W(M);
    std::vector<Vertice> vData(N);
    for (int i = 0; i < M; ++i) {
        std::cin >> U[i] >> D[i] >> W[i];
        --U[i];
    }
    {
        // press
        auto cD = D;
        std::sort(cD.begin(), cD.end());
        cD.erase(std::unique(cD.begin(), cD.end()), cD.end());
        for (auto &e : D) {
            e = (int)(std::lower_bound(cD.begin(), cD.end(), e) - cD.begin());
        }
        K = (int)cD.size();
    }
    for (int i = 0; i < M; ++i) {
        vData[U[i]] = {true, D[i], W[i]};
    }

    auto dfs = [&](auto &&self, const int v) -> std::vector<i64> {
        // calc DP
        std::vector<std::vector<i64>> cDPs;
        for (const int t : tree[v]) {
            cDPs.push_back(self(self, t));
        }
        // cut
        if (cDPs.size() == 1 and not vData[v].exFruit) {
            return cDPs[0];
        }
        std::vector<i64> ret(K + 1);
        for (const auto &vec : cDPs) {
            assert((int)vec.size() == K + 1);
            for (int i = 0; i <= K; ++i) {
                ret[i] += vec[i];
            }
        }
        if (vData[v].exFruit) {
            ret[vData[v].day] += vData[v].weight;
            for (int i = vData[v].day + 1; i <= K; ++i) {
                ret[i] = std::max(ret[i], ret[i - 1]);
            }
        }
        return ret;
    };
    const auto res = dfs(dfs, 0);
    std::cout << res[K] << std::endl;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1891 ms	12172 KB	Output is correct
2	Correct	968 ms	14040 KB	Output is correct
3	Execution timed out	2080 ms	52628 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	440 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Execution timed out	2076 ms	26300 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	115 ms	7884 KB	Output is correct
2	Correct	115 ms	10208 KB	Output is correct
3	Correct	112 ms	16180 KB	Output is correct
4	Correct	94 ms	13576 KB	Output is correct
5	Correct	113 ms	25368 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	102 ms	9384 KB	Output is correct
11	Correct	109 ms	9400 KB	Output is correct
12	Correct	100 ms	15588 KB	Output is correct
13	Correct	85 ms	27096 KB	Output is correct
14	Correct	98 ms	24704 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1640 KB	Output is correct
2	Correct	95 ms	6932 KB	Output is correct
3	Correct	90 ms	6860 KB	Output is correct
4	Correct	115 ms	6964 KB	Output is correct
5	Correct	359 ms	787112 KB	Output is correct
6	Correct	111 ms	9676 KB	Output is correct
7	Correct	85 ms	13404 KB	Output is correct

Subtask #7
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	2 ms	440 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Execution timed out	2076 ms	26300 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	1891 ms	12172 KB	Output is correct
11	Correct	968 ms	14040 KB	Output is correct
12	Execution timed out	2080 ms	52628 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Submission #703486

Compilation message