Submission #603818

#	Time	Username	Problem	Language	Result	Execution time	Memory
603818		strange420	Fireworks (APIO16_fireworks)	C++14	55 / 100	2070 ms	99176 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define MAXNM 300005

int N, M, p, c;
ll cost[MAXNM], totalCost = 0;
vector<int> asd[MAXNM];

struct slope {
        long long gradient;
        long long width;

        slope(long long g, long long w) {
                gradient = g;
                width = w;
        }
};

struct conv_func {
        long long intercept;
        vector<slope> lines;

        conv_func() {
                intercept = 0;
                lines.push_back(slope(1, -1));
        }

        void extend(int c) {
                intercept += c;

                int pt = 0;
                vector<slope> prev;
                while (lines[pt].gradient < -1)
                        prev.push_back(lines[pt++]);

                if (lines[pt].gradient == -1) lines[pt].width += c;
                else prev.push_back(slope(-1, c));

                while (lines[pt].gradient < 1)
                        prev.push_back(lines[pt++]);
                prev.push_back(slope(1, -1));

                lines = prev;
        }

        conv_func merge(conv_func f) {
                conv_func ans, &g = (*this);
                ans.lines.clear();
                ans.intercept = f.intercept + g.intercept;

                int i = 0, j = 0, flag = 1;
                long long ax = 0, bx = 0;
                while(flag) {
                        slope a = f.lines[i];
                        slope b = g.lines[j];
                        slope next_line(a.gradient + b.gradient, -1);

                        long long next_ax = ax + a.width;
                        long long next_bx = bx + b.width;
                        long long prev_x  = max(ax, bx);

                        if (a.width == -1 && b.width == -1) flag = 0;
                        else if (a.width == -1) {
                                next_line.width = next_bx - prev_x;
                                j++; bx = next_bx;
                        } else if (b.width == -1) {
                                next_line.width = next_ax - prev_x;
                                i++; ax = next_ax;
                        } else {
                                next_line.width = min(next_ax, next_bx) - prev_x;
                                if (next_ax <= next_bx) i++, ax = next_ax;
                                if (next_bx <= next_ax) j++, bx = next_bx;
                        }

                        ans.lines.push_back(next_line);
                }

                return ans;
        }
};

conv_func dfs(int u) {
        conv_func ans;
        for (int v: asd[u]) {
                conv_func f = dfs(v);
                f.extend(cost[v]);
                if (ans.lines.size() == 1) ans = f;
                else ans = ans.merge(f);
        }
        return ans;
}

int main() {
        cin >> N >> M;
        for (int i=1; i<N+M; i++) {
                cin >> p >> c;
                asd[p-1].push_back(i);
                cost[i] = c;
        }

        conv_func func = dfs(0);
        long long totalCost = 1e18;
        long long temp = func.intercept;
        for (int i=0; i<func.lines.size(); i++) {
                if (func.lines[i].width == -1) break;

                temp += func.lines[i].width * func.lines[i].gradient;
                totalCost = min(totalCost, temp);
        }
        cout << totalCost << '\n';
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int i=0; i<func.lines.size(); i++) {
      |                       ~^~~~~~~~~~~~~~~~~~

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