oj.uz

Submission #1114210

# Submission time Handle Problem Language Result Execution time Memory
1114210 2024-11-18T11:14:49 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
37 / 100
 87 ms 81992 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 = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                if(vv[mid] <= val)l = mid + 1;
                else
                {
                    ans = mid;
                    r = mid - 1;
                }
            }
            assert(ans != -1);
            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 3 ms 14672 KB Output is correct
4 Correct 3 ms 16888 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 3 ms 16888 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 3 ms 16720 KB Output is correct
9 Correct 3 ms 16720 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 17 ms 17688 KB Output is correct
3 Correct 26 ms 15696 KB Output is correct
4 Correct 30 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 14672 KB Output is correct
2 Incorrect 3 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 70 ms 69704 KB Output is correct
2 Correct 69 ms 69448 KB Output is correct
3 Correct 75 ms 74832 KB Output is correct
4 Correct 59 ms 68552 KB Output is correct
5 Correct 65 ms 81992 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 3 ms 14672 KB Output is correct
4 Correct 3 ms 16888 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 3 ms 16888 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 3 ms 16720 KB Output is correct
9 Correct 3 ms 16720 KB Output is correct
10 Correct 87 ms 69684 KB Output is correct
11 Correct 79 ms 69712 KB Output is correct
12 Correct 82 ms 74936 KB Output is correct
13 Correct 59 ms 70020 KB Output is correct
14 Correct 73 ms 81992 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 3 ms 14672 KB Output is correct
4 Correct 3 ms 16888 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 3 ms 16888 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 3 ms 16720 KB Output is correct
9 Correct 3 ms 16720 KB Output is correct
10 Correct 3 ms 14672 KB Output is correct
11 Incorrect 3 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 3 ms 14672 KB Output is correct
4 Correct 3 ms 16888 KB Output is correct
5 Correct 3 ms 16720 KB Output is correct
6 Correct 3 ms 16888 KB Output is correct
7 Correct 3 ms 16720 KB Output is correct
8 Correct 3 ms 16720 KB Output is correct
9 Correct 3 ms 16720 KB Output is correct
10 Correct 18 ms 16464 KB Output is correct
11 Correct 17 ms 17688 KB Output is correct
12 Correct 26 ms 15696 KB Output is correct
13 Correct 30 ms 15568 KB Output is correct
14 Correct 25 ms 15952 KB Output is correct
15 Correct 3 ms 14672 KB Output is correct
16 Incorrect 3 ms 14672 KB Output isn't correct
17 Halted 0 ms 0 KB -