oj.uz

Submission #1114197

# Submission time Handle Problem Language Result Execution time Memory
1114197 2024-11-18T10:42:42 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 82248 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];
        g[p[i]].push_back(i);
    }
    bool no = 0;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> v[i] >> d[i] >> w[i];
        f[v[i]] = make_pair(d[i], w[i]);
    }

}

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);
        //cout << " beg " << beg << ", day " << day << " : " << cost << " -- > " << dp[beg][day] << endl;

        pref[beg][day] = max(dp[beg][day], pref[beg][day-1]);
       //cout << pref[beg][day] << endl;
    }


}
int main()
{
    speed();

    read();

    vector < pair < int, int > > f;
    vector < pair < int, int > > s;
    long long ans = 0;
    for (auto x: g[1])
    {
        dfs(x, 1);
       // cout << k << " !! " << pref[x][k] << endl;
        ans = ans + pref[x][k];
    }
    cout << ans << endl;
    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 read()':
magictree.cpp:28:10: warning: unused variable 'no' [-Wunused-variable]
   28 |     bool no = 0;
      |          ^~
magictree.cpp: In function 'void dfs(int, int)':
magictree.cpp:56:19: warning: unused variable 'sum' [-Wunused-variable]
   56 |         long long sum = 0;
      |                   ^~~
magictree.cpp:43:15: warning: unused variable 'sum' [-Wunused-variable]
   43 |     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 3 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 69032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 63 ms 67568 KB Output is correct
2 Correct 81 ms 69376 KB Output is correct
3 Correct 62 ms 75080 KB Output is correct
4 Correct 49 ms 68296 KB Output is correct
5 Correct 60 ms 82248 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 3 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 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 80 ms 67664 KB Output is correct
11 Correct 72 ms 67520 KB Output is correct
12 Correct 76 ms 72776 KB Output is correct
13 Correct 55 ms 66244 KB Output is correct
14 Correct 66 ms 80044 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 25672 KB Time limit exceeded
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 3 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 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 6 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 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 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 Execution timed out 2069 ms 69032 KB Time limit exceeded
11 Halted 0 ms 0 KB -