oj.uz

Submission #1114200

# Submission time Handle Problem Language Result Execution time Memory
1114200 2024-11-18T10:54:56 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
37 / 100
 91 ms 80228 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];
map < int, int > decode;
long long leaf[MAXN], total = 0;
int maxindex = 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;
    vector < int > diffw;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> v[i] >> d[i] >> w[i];
        diffw.push_back(d[i]);
        if(!leaf[v[i]])no = 1;
        total += w[i];
        f[v[i]] = make_pair(d[i], w[i]);
    }
    sort(diffw.begin(), diffw.end());
    int newid = 0, last = -1;
    for(auto x: diffw)
    {
        if(last == x)continue;
        newid ++;
        decode[x] = newid;
        last = x;
    }
    if(!no)
    {
        cout << total << endl;
        exit(0);
    }
    for (int i = 1; i <= n; ++ i)
    {
        f[i].first = decode[f[i].first];
       // cout << f[i].first << endl;
    }
    k = newid;
   // cout << k << endl;
}

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 <= 1000)
    {
        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:81:19: warning: unused variable 'sum' [-Wunused-variable]
   81 |         long long sum = 0;
      |                   ^~~
magictree.cpp:69:15: warning: unused variable 'sum' [-Wunused-variable]
   69 |     long long sum = 0;
      |               ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15868 KB Output is correct
2 Correct 18 ms 16464 KB Output is correct
3 Correct 40 ms 16832 KB Output is correct
4 Correct 36 ms 16460 KB Output is correct
5 Correct 44 ms 16840 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 17232 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 68 ms 67744 KB Output is correct
2 Correct 77 ms 67420 KB Output is correct
3 Correct 68 ms 72928 KB Output is correct
4 Correct 59 ms 66560 KB Output is correct
5 Correct 67 ms 80060 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 2 ms 14672 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 4 ms 14672 KB Output is correct
10 Correct 87 ms 67792 KB Output is correct
11 Correct 81 ms 67688 KB Output is correct
12 Correct 91 ms 73056 KB Output is correct
13 Correct 69 ms 67564 KB Output is correct
14 Correct 76 ms 80228 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 2 ms 14672 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 4 ms 14672 KB Output is correct
10 Incorrect 5 ms 17232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 2 ms 14672 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 4 ms 14672 KB Output is correct
10 Correct 22 ms 15868 KB Output is correct
11 Correct 18 ms 16464 KB Output is correct
12 Correct 40 ms 16832 KB Output is correct
13 Correct 36 ms 16460 KB Output is correct
14 Correct 44 ms 16840 KB Output is correct
15 Incorrect 5 ms 17232 KB Output isn't correct
16 Halted 0 ms 0 KB -