제출 #205907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205907		himyu	Fireworks (APIO16_fireworks)	C++17	26 / 100	11 ms	7544 KiB

fireworks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

template <class T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<pli> adj[300001];
const i64 inf = numeric_limits<i64>::max() / 3;

inline i64 ab(i64 x) { return x > 0 ? x : -x; }

class slope {
   public:
    vector<i64> bp;
    i64 sac, pen;

    slope() {
        bp.clear();
        sac = 0, pen = 0;
    }

    void push(i64 x) {
        if (bp.empty()) {
            bp.emplace_back(x);
            bp.emplace_back(x);
            ++sac;
            return;
        }

        while (bp.size() > sac + 1) bp.pop_back();
        bp[sac] += x;
        bp[sac - 1] += x;
    }

    i64 get(int x) const {
        if (bp.empty()) return 0;

        i64 ret = 0;
        if (x > bp[sac])
            for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
        if (x < bp[sac - 1])
            for (int i = sac - 1; i >= 0; i--) ret += max(bp[i] - x, 0LL);
        return ret;
    }

    void print() {
        cout << "sac: " << sac << endl;
        cout << "pen: " << pen << endl;
        cout << "bp: ";
        for (auto el : bp) cout << el << " ";
        cout << endl;
    }
};

slope mer(const vector<slope> &sl) {
    slope ret;

    for (auto &sp : sl) {
        ret.sac += sp.sac;
        ret.pen += sp.pen;
    }

    for (auto &sp : sl) {
        for (auto el : sp.bp) {
            ret.bp.emplace_back(el);
        }
    }
    sort(iterall(ret.bp));

    for (auto &sp : sl) ret.pen += sp.get(ret.bp[ret.sac]);
    return ret;
}

slope solve(int h, int p = -1) {
    vector<slope> tomer;
    for (auto [t, wf] : adj[h]) {
        if (t == p) continue;
        auto chslp = solve(t, h);
        chslp.push(wf);
        tomer.emplace_back(chslp);
    }

    return mer(tomer);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 2; i <= N + M; i++) {
        i64 j, w;
        cin >> j >> w;

        adj[i].emplace_back(j, w);
        adj[j].emplace_back(i, w);
    }

    cout << solve(1).pen << endl;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In member function 'void slope::push(i64)':
fireworks.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (bp.size() > sac + 1) bp.pop_back();
                ~~~~~~~~~~^~~~~~~~~
fireworks.cpp: In member function 'i64 slope::get(int) const':
fireworks.cpp:55:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
                               ~~^~~~~~~~~~~

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