oj.uz

Submission #598589

# Submission time Handle Problem Language Result Execution time Memory
598589 2022-07-18T14:31:50 Z Valaki2 Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 32212 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int maxn = 1e5;

struct fruit {
    int vertex, day, weight;
    fruit() : vertex(0), day(0), weight(0) {}
    fruit(int vertex_, int day_, int weight_) :
        vertex(vertex_), day(day_), weight(weight_) {}
};

int n, m, k;
int par[maxn + 1];
vector<int> children[maxn + 1];
bool has_fruit[maxn + 1];
fruit fruit_of[maxn + 1];
vector<fruit> fruits;
int dp[maxn + 1];
set<int> days;

vector<int> init_dfs(int cur) {
    vector<int> v;
    for(int nei : children[cur]) {
        vector<int> v2 = init_dfs(nei);
        for(int x : v2) {
            v.pb(x);
        }
    }
    if(has_fruit[cur] || cur == 1) {
        children[cur] = v;
        return vector<int> (1, cur);
    }
    return v;
}

void dfs(int cur, int &d) {
    int sum = 0;
    for(int nei : children[cur]) {
        dfs(nei, d);
        sum += dp[nei];
    }
    if(has_fruit[cur] && fruit_of[cur].day == d) {
        sum += fruit_of[cur].weight;
    }
    dp[cur] = max(dp[cur], sum);
}

void solve() {
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i++) {
        cin >> par[i];
        children[par[i]].pb(i);
    }
    fruits.assign(m, fruit());
    for(int i = 0; i < m; i++) {
        cin >> fruits[i].vertex >> fruits[i].day >> fruits[i].weight;
        has_fruit[fruits[i].vertex] = true;
        days.insert(fruits[i].day);
        fruit_of[fruits[i].vertex] = fruits[i];
    }
    init_dfs(1);
    for(int d : days) {
        dfs(1, d);
    }
    cout << dp[1] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 10472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5204 KB Output is correct
2 Correct 5 ms 5204 KB Output is correct
3 Correct 4 ms 5272 KB Output is correct
4 Execution timed out 2100 ms 32212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10796 KB Output is correct
2 Correct 66 ms 10656 KB Output is correct
3 Correct 69 ms 18256 KB Output is correct
4 Correct 35 ms 10228 KB Output is correct
5 Correct 57 ms 29056 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 140 ms 10680 KB Output is correct
11 Correct 126 ms 10696 KB Output is correct
12 Correct 123 ms 18180 KB Output is correct
13 Correct 51 ms 10364 KB Output is correct
14 Correct 84 ms 29024 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5812 KB Output is correct
2 Correct 28 ms 8532 KB Output is correct
3 Correct 29 ms 9168 KB Output is correct
4 Correct 35 ms 9164 KB Output is correct
5 Correct 26 ms 7736 KB Output is correct
6 Correct 42 ms 12448 KB Output is correct
7 Correct 54 ms 16768 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 4 ms 5272 KB Output is correct
13 Execution timed out 2100 ms 32212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Execution timed out 2055 ms 10472 KB Time limit exceeded
11 Halted 0 ms 0 KB -