Submission #728104

#	Time	Username	Problem	Language	Result	Execution time	Memory
728104		josanneo22	Fireworks (APIO16_fireworks)	C++17	100 / 100	318 ms	74420 KiB

fireworks

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const lint inf = 1e16;

int n, m, sz[300005];
lint dep[300005], c[300005];

vector<int> gph[300005];

struct func {
    priority_queue<lint> pq;
    lint cost;
    int slope;
    void init() {
        cost = 0;
        slope = -1;
        pq.push(0);
        pq.push(0);
    }
    void upperize(int x) {
        cost += c[x];
        while (!pq.empty() && slope + (int)pq.size() > 1) {
            pq.pop();
        }
        vector<lint> v;
        while (!pq.empty() && slope + (int)pq.size() >= 0) {
            v.push_back(pq.top());
            pq.pop();
        }
        while (!v.empty()) {
            pq.push(v.back() + c[x]);
            v.pop_back();
        }
    }
}dp[300005];

bool cmp(int a, int b) {
    return sz[a] > sz[b];
}

void dfs(int x) {
    if (x > n) {
        sz[x] = 1;
        return;
    }
    for (int i = 0; i < gph[x].size(); i++) {
        dep[gph[x][i]] = dep[x] + c[gph[x][i]];
        dfs(gph[x][i]);
        sz[x] += sz[gph[x][i]];
    }
    sort(gph[x].begin(), gph[x].end(), cmp);
}

int solve(int x) {
    if (x > n) {
        dp[x].init();
        return x;
    }
    int ret = solve(gph[x][0]);
    dp[ret].upperize(gph[x][0]);
    for (int i = 1; i < gph[x].size(); i++) {
        int t = solve(gph[x][i]);
        dp[t].upperize(gph[x][i]);
        dp[ret].cost += dp[t].cost;
        dp[ret].slope += dp[t].slope;
        while (!dp[t].pq.empty()) {
            dp[ret].pq.push(dp[t].pq.top());
            dp[t].pq.pop();
        }
    }
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 2; i <= n + m; i++) {
        int p;
        scanf("%d %lld", &p, &c[i]);
        gph[p].push_back(i);
    }
    dfs(1);
    func ret = dp[solve(1)];
    ret.upperize(0);
    lint ansp = ret.pq.top();
    lint ans = ret.cost + ansp * ret.slope;
    while (!ret.pq.empty()) {
        ans += ansp - ret.pq.top();
        ret.pq.pop();
    }
    printf("%lld", ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < gph[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'int solve(int)':
fireworks.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 1; i < gph[x].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %lld", &p, &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45