oj.uz

Submission #712742

# Submission time Handle Problem Language Result Execution time Memory
712742 2023-03-19T16:35:22 Z noedit Magic Tree (CEOI19_magictree) C++17
34 / 100
 404 ms 1048576 KB 
#include <bits/stdc++.h>
//#include <quadmath.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
using namespace __gnu_pbds;

//#define int long long
//#define ld long double
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

const int INF = 2e9;

vector<vector<int> > g;

vector<pair<int, int> > a;

vector<vector<ll> > dp;

int k;

void dfs(int v, int p)
{
    for (auto& u : g[v])
    {
        if (u != p)
        {
            dfs(u, v);
        }
    }
    ll bebra = 0;
    if (a[v].first != INF){
    for (auto& u : g[v])
    {
        if (u != p)
            bebra += dp[u][a[v].first];
    }
    }
    for (int i = 1; i <= k; i++)
    {
        ll res = 0;
        for (auto& u : g[v]){
            if (u != p)
            res += dp[u][i];
        }
        dp[v][i] = res;
        if (a[v].first <= i)
        {
            dp[v][i] = max(dp[v][i], bebra + a[v].second);
        }
    }

}

void solve()
{
    int n, m;
    cin >> n >> m >> k;
    g.resize(n);
    a.resize(n, {INF, 0});
    dp.resize(n, vector<ll>(k + 1));
    for (int i = 1; i < n; i++)
    {
        int p;
        cin >> p;
        p--;
        g[p].push_back(i);
    }
    for (int i = 0; i < m; i++)
    {
        int v, d, w;
        cin >> v >> d >> w;
        v--;
        a[v] = {d, w};
    }
    dfs(0, 0);
    ll ans = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cout << i << ": ";
//        for (int j = 1; j <= k; j++)
//        {
//            cout << dp[i][j] << ' ';
//        }
//        cout << endl;
//    }
    for (int i = 1; i <= k; i++) ans = max(ans, dp[0][i]);
    cout << ans;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3
*/

/*
4
1 3
2 4
2 3
3 4

*/

/*
1 1 1
100000000 1 1 1
1 1
*/

/*
????????????????????????????????????????????????
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 404 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 6 ms 8264 KB Output is correct
3 Correct 6 ms 8276 KB Output is correct
4 Runtime error 368 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12580 KB Output is correct
2 Correct 58 ms 12548 KB Output is correct
3 Correct 57 ms 16076 KB Output is correct
4 Correct 35 ms 11112 KB Output is correct
5 Correct 48 ms 20392 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 81 ms 26112 KB Output is correct
11 Correct 65 ms 18120 KB Output is correct
12 Correct 60 ms 29452 KB Output is correct
13 Correct 55 ms 24560 KB Output is correct
14 Correct 51 ms 33868 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 377 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 6 ms 8264 KB Output is correct
12 Correct 6 ms 8276 KB Output is correct
13 Runtime error 368 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 212 KB Output is correct
10 Runtime error 404 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -