oj.uz

Submission #659412

# Submission time Handle Problem Language Result Execution time Memory
659412 2022-11-17T16:34:10 Z mychecksedad Magic Tree (CEOI19_magictree) C++17
34 / 100
 91 ms 59176 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 25;



int n, m, k, t[N];
vector<int> g[N];
ll w[N], dp[N][K];

void dfs(int v, int p){
    for(int i = 0; i < K; ++i) dp[v][i] = 0;
    for(int u: g[v]){
        dfs(u, v);
        for(int i = 1; i < K; ++i) dp[v][i] += dp[u][i];
    }
    dp[v][t[v]] += w[v];
    for(int i = 1; i < K; ++i) dp[v][i] = max(dp[v][i], dp[v][i - 1]);
}


void solve(){
    cin >> n >> m >> k;
    for(int i = 2; i <= n; ++i){
        int p; cin >> p;
        g[p].pb(i);
    }
    for(int i = 0; i <= n; ++i) t[i] = w[i] = 0;
    for(int i = 0; i < m; ++i){
        int v, d, e; cin >> v >> d >> e;
        t[v] = d;
        w[v] = e;
    }


    dfs(1, 0);


    cout << *max_element(dp[1] + 1, dp[1] + K);
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:60:16: warning: unused variable 'aa' [-Wunused-variable]
   60 |     int T = 1, aa;
      |                ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23868 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23776 KB Output is correct
7 Correct 12 ms 23756 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 46624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24068 KB Output is correct
2 Incorrect 12 ms 24176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 46176 KB Output is correct
2 Correct 82 ms 48212 KB Output is correct
3 Correct 76 ms 52948 KB Output is correct
4 Correct 58 ms 46760 KB Output is correct
5 Correct 67 ms 59176 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23868 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23776 KB Output is correct
7 Correct 12 ms 23756 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 80 ms 47640 KB Output is correct
11 Correct 91 ms 47564 KB Output is correct
12 Correct 72 ms 52192 KB Output is correct
13 Correct 55 ms 46100 KB Output is correct
14 Correct 60 ms 58560 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 28356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23868 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23776 KB Output is correct
7 Correct 12 ms 23756 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 24068 KB Output is correct
11 Incorrect 12 ms 24176 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23868 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23704 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23776 KB Output is correct
7 Correct 12 ms 23756 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Incorrect 68 ms 46624 KB Output isn't correct
11 Halted 0 ms 0 KB -