oj.uz

Submission #1114195

# Submission time Handle Problem Language Result Execution time Memory
1114195 2024-11-18T10:37:45 Z n3rm1n Magic Tree (CEOI19_magictree) C++17
22 / 100
 2000 ms 79904 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 ++;
        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 3 ms 14672 KB Output is correct
3 Correct 3 ms 12792 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 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 3 ms 12792 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 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 88 ms 69036 KB Output is correct
11 Correct 84 ms 68936 KB Output is correct
12 Correct 89 ms 73704 KB Output is correct
13 Correct 60 ms 67272 KB Output is correct
14 Correct 75 ms 79904 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 25704 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 3 ms 14672 KB Output is correct
3 Correct 3 ms 12792 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 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Incorrect 7 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 3 ms 14672 KB Output is correct
3 Correct 3 ms 12792 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 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Execution timed out 2059 ms 68936 KB Time limit exceeded
11 Halted 0 ms 0 KB -