oj.uz

Submission #953569

# Submission time Handle Problem Language Result Execution time Memory
953569 2024-03-26T08:31:45 Z LucaIlie Magic Tree (CEOI19_magictree) C++17
34 / 100
 133 ms 45036 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] = 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.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 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 9560 KB Output is correct
2 Incorrect 4 ms 9560 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 127 ms 30028 KB Output is correct
2 Correct 126 ms 29268 KB Output is correct
3 Correct 133 ms 35152 KB Output is correct
4 Correct 99 ms 30920 KB Output is correct
5 Correct 97 ms 45036 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9308 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 2 ms 9308 KB Output is correct
10 Correct 126 ms 33872 KB Output is correct
11 Correct 115 ms 32592 KB Output is correct
12 Correct 103 ms 35268 KB Output is correct
13 Correct 78 ms 30668 KB Output is correct
14 Correct 85 ms 44884 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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