Submission #953573

#	Time	Username	Problem	Language	Result	Execution time	Memory
953573		LucaIlie	Magic Tree (CEOI19_magictree)	C++17	100 / 100	168 ms	36312 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];

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].upper_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] - sum;
    }
}

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 << sum;

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17