oj.uz

Submission #1114206

# Submission time Handle Problem Language Result Execution time Memory
1114206 2024-11-18T11:13:03 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
37 / 100
 88 ms 82088 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;
long long a[MAXN];
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];
        a[v[i]] = d[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]);
    }
}
vector < int > vv;
void solve11()
{
    vv.push_back(0);
    for (int i = n; i >= 2; -- i)
    {
        int val = a[i];
        if(!val)continue;
        int sz = vv.size();
        if(vv[sz-1] <= val)vv.push_back(val);
        else
        {
            int l = 0, r = sz-1, mid, ans = 0;
            while(l <= r)
            {
                mid = (l + r)/2;
                if(vv[mid] <= val)l = mid + 1;
                else
                {
                    ans = mid;
                    r = mid - 1;
                }
            }
            if(ans)vv[mid] = val;
        }

    }
    cout << vv.size()-1 << endl;
}
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;
    }


   solve11();
    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

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



*/

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16464 KB Output is correct
2 Correct 21 ms 17488 KB Output is correct
3 Correct 28 ms 16096 KB Output is correct
4 Correct 21 ms 15568 KB Output is correct
5 Correct 25 ms 15952 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14840 KB Output is correct
2 Incorrect 2 ms 14672 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 71 ms 69712 KB Output is correct
2 Correct 71 ms 69448 KB Output is correct
3 Correct 68 ms 74824 KB Output is correct
4 Correct 53 ms 68492 KB Output is correct
5 Correct 67 ms 81996 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 2 ms 16720 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 16888 KB Output is correct
10 Correct 88 ms 69704 KB Output is correct
11 Correct 83 ms 69644 KB Output is correct
12 Correct 81 ms 74824 KB Output is correct
13 Correct 60 ms 70024 KB Output is correct
14 Correct 72 ms 82088 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 15184 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 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 2 ms 16720 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 16888 KB Output is correct
10 Correct 3 ms 14840 KB Output is correct
11 Incorrect 2 ms 14672 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 16720 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 2 ms 16720 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 16888 KB Output is correct
10 Correct 18 ms 16464 KB Output is correct
11 Correct 21 ms 17488 KB Output is correct
12 Correct 28 ms 16096 KB Output is correct
13 Correct 21 ms 15568 KB Output is correct
14 Correct 25 ms 15952 KB Output is correct
15 Correct 3 ms 14840 KB Output is correct
16 Incorrect 2 ms 14672 KB Output isn't correct
17 Halted 0 ms 0 KB -