oj.uz

Submission #147454

# Submission time Handle Problem Language Result Execution time Memory
147454 2019-08-29T15:17:34 Z dolphingarlic Fireworks (APIO16_fireworks) C++14
0 / 100
 19 ms 14812 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    ll a, b, c;
    priority_queue<ll> *pq;
};

Node dp[300001];
vector<int> graph[300001];

void dfs(int node = 1) {
    if (graph[node].size()) {
        int mx_cnt = 0, mx_child = 0;
        for (int i : graph[node]) {
            dfs(i);
            dp[node].a += dp[i].a;
            dp[node].b += dp[i].b;
            if (dp[i].pq->size() > mx_cnt)
                mx_cnt = dp[i].pq->size(), mx_child = i;
        }

        dp[node].pq = dp[mx_child].pq;
        for (int i : graph[node])
            if (i != mx_child)
                while (dp[i].pq->size()) {
                    dp[node].pq->push(dp[i].pq->top());
                    dp[i].pq->pop();
                }

        while (dp[node].a > 1) {
            dp[node].a--;
            dp[node].b += dp[node].pq->top();
            dp[node].pq->pop();
        }

        ll slope1 = dp[node].pq->top();
        dp[node].pq->pop();
        ll slope0 = dp[node].pq->top();
        dp[node].pq->pop();
        
        dp[node].pq->push(slope1 + dp[node].c);
        dp[node].pq->push(slope0 + dp[node].c);

        dp[node].b -= dp[node].c;
    } else {
        dp[node].a = 1, dp[node].b = -dp[node].c;
        dp[node].pq->push(dp[node].c);
        dp[node].pq->push(dp[node].c);
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    FOR(i, 2, n + m + 1) {
        int p, c;
        cin >> p >> c;
        graph[p].push_back(i);
        dp[i].c = c;
    }

    dfs();
    if (dp[1].a) dp[1].b += dp[1].pq->top();

    cout << dp[1].b;
    return 0;
}

Compilation message

fireworks.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:22:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (dp[i].pq->size() > mx_cnt)
                 ~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 14812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 14712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 14812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 14812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -