oj.uz

Submission #953572

# Submission time Handle Problem Language Result Execution time Memory
953572 2024-03-26T08:47:36 Z LucaIlie Magic Tree (CEOI19_magictree) C++17
16 / 100
 154 ms 33364 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] - 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Incorrect 3 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 69 ms 17236 KB Output is correct
2 Correct 58 ms 19788 KB Output is correct
3 Correct 154 ms 33364 KB Output is correct
4 Correct 106 ms 18364 KB Output is correct
5 Correct 133 ms 20056 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 103 ms 13652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8008 KB Output is correct
2 Correct 41 ms 10668 KB Output is correct
3 Correct 40 ms 10692 KB Output is correct
4 Correct 31 ms 10540 KB Output is correct
5 Correct 16 ms 8916 KB Output is correct
6 Correct 34 ms 13760 KB Output is correct
7 Correct 36 ms 18260 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Incorrect 3 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 2 ms 7260 KB Output is correct
2 Incorrect 3 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -