oj.uz

Submission #953565

# Submission time Handle Problem Language Result Execution time Memory
953565 2024-03-26T08:22:35 Z LucaIlie Magic Tree (CEOI19_magictree) C++17
3 / 100
 163 ms 35788 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];

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" );*/
}

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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 18388 KB Output is correct
2 Correct 59 ms 20372 KB Output is correct
3 Correct 163 ms 35788 KB Output is correct
4 Correct 100 ms 20020 KB Output is correct
5 Correct 134 ms 22344 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -