oj.uz

Submission #598585

# Submission time Handle Problem Language Result Execution time Memory
598585 2022-07-18T14:26:19 Z Valaki2 Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 24768 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;

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];
    }
    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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5040 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 2056 ms 10032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5076 KB Output is correct
2 Correct 8 ms 5076 KB Output is correct
3 Correct 8 ms 5192 KB Output is correct
4 Execution timed out 2059 ms 24768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10656 KB Output is correct
2 Correct 68 ms 12736 KB Output is correct
3 Correct 56 ms 16560 KB Output is correct
4 Correct 37 ms 11372 KB Output is correct
5 Correct 61 ms 21836 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5040 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 174 ms 12064 KB Output is correct
11 Correct 107 ms 12052 KB Output is correct
12 Correct 131 ms 15908 KB Output is correct
13 Correct 45 ms 10824 KB Output is correct
14 Correct 90 ms 21184 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 5776 KB Output is correct
2 Execution timed out 2078 ms 9056 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5040 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 2056 ms 10032 KB Time limit exceeded
11 Halted 0 ms 0 KB -