oj.uz

Submission #953567

# Submission time Handle Problem Language Result Execution time Memory
953567 2024-03-26T08:27:46 Z LucaIlie Magic Tree (CEOI19_magictree) C++17
34 / 100
 127 ms 47076 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
bool hasFruit[MAX_N + 1];
int fruitTime[MAX_N + 1], fruitWeight[MAX_N + 1];
vector<int> adj[MAX_N + 1];
map<int, long long> dif[MAX_N + 1];
long long dp[MAX_N + 1][21];

void dfs( int u ) {
    int h = 0;
    for ( int v: adj[u] ) {
        dfs( v );
        if ( h == 0 || dif[v].size() > dif[h].size() )
            h = v;
    }

    if ( h != 0 ) {
        swap( dif[u], dif[h] );

        for ( int v: adj[u] ) {
            if ( v == h )
                continue;

            for ( auto p: dif[v] )
                dif[u][p.first] += p.second;
        }
    }

    if ( hasFruit[u] ) {
        auto p = dif[u].lower_bound( fruitTime[u] );
        long long sum = 0;
        vector<int> del;
        while ( p != dif[u].end() && fruitWeight[u] > sum + p->second ) {
            sum += p->second;
            del.push_back( p->first );
            p++;
        }
        for ( int t: del )
            dif[u].erase( t );
        dif[u][fruitTime[u]] += fruitWeight[u];
        if ( p != dif[u].end() )
            dif[u][p->first] -= fruitWeight[u];
    }


    /*printf( "%d:\n", u );
    for ( auto p: dif[u] )
        printf( "%d %d\n", p.first, p.second );
    printf( "\n\n" );*/

    for ( int d = 0; d <= 20; d++ ) {
        dp[u][d] = (fruitTime[u] == d ? fruitWeight[u] : 0);
        for ( int v: adj[u] )
            dp[u][d] += dp[v][d];
        if ( d > 0 )
            dp[u][d] = max( dp[u][d], dp[u][d - 1] );
    }
}

int main() {
    int n, m, k;

    cin >> n >> m >> k;
    for ( int v = 2; v <= n; v++ ) {
        int p;
        cin >> p;
        adj[p].push_back( v );
    }

    for ( int i = 0; i < m; i++ ) {
        int v;
        cin >> v;
        hasFruit[v] = true;
        cin >> fruitTime[v] >> fruitWeight[v];
    }

    dfs( 1 );

    long long sum = 0;
    for ( auto p: dif[1] )
        sum += p.second;

    cout << dp[1][20];

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9360 KB Output is correct
7 Correct 2 ms 9316 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9564 KB Output is correct
2 Incorrect 3 ms 9564 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 123 ms 30124 KB Output is correct
2 Correct 123 ms 31280 KB Output is correct
3 Correct 118 ms 37200 KB Output is correct
4 Correct 90 ms 32388 KB Output is correct
5 Correct 98 ms 47076 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9360 KB Output is correct
7 Correct 2 ms 9316 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 127 ms 35412 KB Output is correct
11 Correct 119 ms 34240 KB Output is correct
12 Correct 97 ms 36688 KB Output is correct
13 Correct 87 ms 31888 KB Output is correct
14 Correct 88 ms 46420 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9360 KB Output is correct
7 Correct 2 ms 9316 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Incorrect 3 ms 9564 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9360 KB Output is correct
7 Correct 2 ms 9316 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Incorrect 97 ms 33876 KB Output isn't correct
11 Halted 0 ms 0 KB -