oj.uz

Submission #723640

# Submission time Handle Problem Language Result Execution time Memory
723640 2023-04-14T06:52:35 Z dxz05 Magic Tree (CEOI19_magictree) C++17
50 / 100
 1654 ms 791456 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

vector<int> g[N];

vector<vector<ll>> dp;
pair<int, int> fruit[N];

void dfs(int v){
    dp[v][fruit[v].first] = fruit[v].second;

    for (int u : g[v]){
        dfs(u);
    }

    for (int t = 1; t < dp[v].size(); t++){
        for (int u : g[v]){
            dp[v][t] += dp[u][t];
        }
    }

    for (int t = 1; t < dp[v].size(); t++) dp[v][t] = max(dp[v][t], dp[v][t - 1]);

}

void solve(){
    int n, m, k;
    cin >> n >> m >> k;

    ll sum = 0;
    for (int i = 1; i < n; i++){
        int p;
        cin >> p;
        --p;
        g[p].push_back(i);
    }

    map<int, int> mp;

    for (int i = 0; i < m; i++){
        int v, d, w;
        cin >> v >> d >> w;
        --v;
        mp[d];
        fruit[v] = MP(d, w);
        sum += w;
    }

    mp[0];
    k = 0;
    for (auto &now : mp){
        now.second = ++k;
    }

    for (int i = 0; i < n; i++){
        fruit[i].first = mp[fruit[i].first];
    }
    
    if (k > 1000){
        cout << sum << endl;
        return;
    }

    dp.assign(n, vector<ll>(k + 1, 0));

    dfs(0);

    cout << dp[0].back() << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Compilation message

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int t = 1; t < dp[v].size(); t++){
      |                     ~~^~~~~~~~~~~~~~
magictree.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int t = 1; t < dp[v].size(); t++) dp[v][t] = max(dp[v][t], dp[v][t - 1]);
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5848 KB Output is correct
2 Correct 33 ms 6820 KB Output is correct
3 Correct 84 ms 6952 KB Output is correct
4 Correct 73 ms 6716 KB Output is correct
5 Correct 79 ms 6988 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5844 KB Output is correct
2 Correct 7 ms 5940 KB Output is correct
3 Correct 5 ms 5844 KB Output is correct
4 Incorrect 55 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12116 KB Output is correct
2 Correct 63 ms 10456 KB Output is correct
3 Correct 63 ms 14788 KB Output is correct
4 Correct 40 ms 10920 KB Output is correct
5 Correct 48 ms 18212 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 82 ms 26212 KB Output is correct
11 Correct 62 ms 18260 KB Output is correct
12 Correct 70 ms 28872 KB Output is correct
13 Correct 57 ms 24984 KB Output is correct
14 Correct 62 ms 32460 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 127928 KB Output is correct
2 Correct 663 ms 607180 KB Output is correct
3 Correct 661 ms 610336 KB Output is correct
4 Correct 849 ms 788744 KB Output is correct
5 Correct 1654 ms 787496 KB Output is correct
6 Correct 836 ms 789360 KB Output is correct
7 Correct 806 ms 791456 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 5 ms 5844 KB Output is correct
11 Correct 7 ms 5940 KB Output is correct
12 Correct 5 ms 5844 KB Output is correct
13 Incorrect 55 ms 9684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 37 ms 5848 KB Output is correct
11 Correct 33 ms 6820 KB Output is correct
12 Correct 84 ms 6952 KB Output is correct
13 Correct 73 ms 6716 KB Output is correct
14 Correct 79 ms 6988 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 7 ms 5940 KB Output is correct
17 Correct 5 ms 5844 KB Output is correct
18 Incorrect 55 ms 9684 KB Output isn't correct
19 Halted 0 ms 0 KB -