Submission #953569

#	Time	Username	Problem	Language	Result	Execution time	Memory
953569		LucaIlie	Magic Tree (CEOI19_magictree)	C++17	34 / 100	133 ms	45036 KiB

magictree

#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] = 0;
        for ( int v: adj[u] )
            dp[u][d] += dp[v][d];
    }
    int d = fruitTime[u];
    while ( d <= 20 && dp[u][d] < dp[u][fruitTime[u]] + fruitWeight[u] )
        d++;
    for ( int i = d - 1; i >= fruitTime[u]; i-- )
        dp[u][i] = dp[u][fruitTime[u]] + fruitWeight[u];
}

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 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17