oj.uz

Submission #1114198

# Submission time Handle Problem Language Result Execution time Memory
1114198 2024-11-18T10:48:55 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
37 / 100
 83 ms 79944 KB 
#include<bits/stdc++.h>
//define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10, MAXK = 22;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
int p[MAXN];
long long v[MAXN], d[MAXN], w[MAXN];
vector < int > g[MAXN];
pair < int, int > f[MAXN];
long long leaf[MAXN], total = 0;

void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++ i)
        leaf[i] = 1;
    for (int i = 2; i <= n; ++ i)
    {
        cin >> p[i];
        leaf[p[i]] = 0;
        g[p[i]].push_back(i);
    }
    bool no = 0;
    long long total = 0;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> v[i] >> d[i] >> w[i];
        if(!leaf[v[i]])no = 1;
        total += w[i];
        f[v[i]] = make_pair(d[i], w[i]);
    }
    if(!no)
    {
        cout << total << endl;
        exit(0);
    }
}

long long sub[MAXN][MAXK], dp[MAXN][MAXK], pref[MAXN][MAXK];
void dfs(int beg, int par)
{
    int dd = f[beg].first;
    if(dd)sub[beg][dd] += f[beg].second;
    long long sum = 0;
    for (auto nb: g[beg])
    {
        if(nb == par)continue;
        dfs(nb, beg);
        for (int i = 1; i <= k; ++ i)
            sub[beg][i] += sub[nb][i];
    }
    for (int day = 1; day <= k; ++ day)
    {
        long long cost = 0;
        if(day == dd)cost += f[beg].second;
        long long sum = 0;
        for (auto nb: g[beg])
            cost += max(pref[nb][day], sub[nb][day]);
        dp[beg][day] = max(dp[beg][day], cost);
        pref[beg][day] = max(dp[beg][day], pref[beg][day-1]);
    }
}
int main()
{
    speed();

    read();

    if(k <= 20)
    {
        long long ans = 0;
        for (auto x: g[1])
        {
            dfs(x, 1);
            ans = ans + pref[x][k];
        }
        cout << ans << endl;
        return 0;
    }
    return 0;
}
/***
7 5 2
1 2 2 1 4 4
2 2 1
3 2 1
4 1 1
6 1 1
5 1 10

6 5 10
1 2 2 1 1
2 2 8
3 5 6
4 5 7
5 10 1
6 10 1



*/

Compilation message

magictree.cpp: In function 'void dfs(int, int)':
magictree.cpp:62:19: warning: unused variable 'sum' [-Wunused-variable]
   62 |         long long sum = 0;
      |                   ^~~
magictree.cpp:50:15: warning: unused variable 'sum' [-Wunused-variable]
   50 |     long long sum = 0;
      |               ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14596 KB Output is correct
2 Correct 16 ms 15440 KB Output is correct
3 Correct 28 ms 13648 KB Output is correct
4 Correct 23 ms 13520 KB Output is correct
5 Correct 29 ms 13916 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 67656 KB Output is correct
2 Correct 67 ms 67400 KB Output is correct
3 Correct 61 ms 72776 KB Output is correct
4 Correct 51 ms 66504 KB Output is correct
5 Correct 83 ms 79944 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14840 KB Output is correct
6 Correct 2 ms 14672 KB Output is correct
7 Correct 2 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 83 ms 67656 KB Output is correct
11 Correct 74 ms 67656 KB Output is correct
12 Correct 79 ms 72776 KB Output is correct
13 Correct 59 ms 66164 KB Output is correct
14 Correct 69 ms 79944 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14840 KB Output is correct
6 Correct 2 ms 14672 KB Output is correct
7 Correct 2 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Incorrect 3 ms 12624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14840 KB Output is correct
6 Correct 2 ms 14672 KB Output is correct
7 Correct 2 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 18 ms 14596 KB Output is correct
11 Correct 16 ms 15440 KB Output is correct
12 Correct 28 ms 13648 KB Output is correct
13 Correct 23 ms 13520 KB Output is correct
14 Correct 29 ms 13916 KB Output is correct
15 Incorrect 3 ms 12624 KB Output isn't correct
16 Halted 0 ms 0 KB -