제출 #1283135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283135		herominhsteve	Harbingers (CEOI09_harbingers)	C++20	40 / 100	1097 ms	40268 KiB

harbingers

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

#define el '\n'
#define FNAME "harbingers"
using ll = long long;

const int MAXN = 100000 + 5;
const ll INFLL = (ll)1e16 + 15092007;

struct MinHull {
    struct Line {
        ll a, b; 
        Line() : a(0), b(0) {}
        Line(ll A, ll B) : a(A), b(B) {}
        ll eval(ll x) const { return a * x + b; }
    };

    struct HistEntry {
        bool isPop;
        Line ln;
        long double bubble;   
        bool addedBubble;     
    };

    vector<Line> lines;        
    vector<long double> bubble;
    vector<HistEntry> history;

    static long double intersect(const Line &L1, const Line &L2) {
        return (long double)(L2.b - L1.b) / (long double)(L1.a - L2.a);
    }

    static bool bad(const Line &A, const Line &B, const Line &C) {
        long double x1 = intersect(A, B);
        long double x2 = intersect(B, C);
        return x2 <= x1;
    }

    int checkpoint() const { return (int)history.size(); }

    void addLine(ll a, ll b) {
        Line L(a, b);
        while (lines.size() >= 2 && bad(lines[lines.size()-2], lines.back(), L)) {
            history.push_back({ true, lines.back(), bubble.back(), false });
            lines.pop_back();
            bubble.pop_back();
        }

        bool willPushBubble = !lines.empty();
        long double newBubble = 0;
        if (willPushBubble) {
            newBubble = intersect(lines.back(), L);
            bubble.push_back(newBubble);
        }
        lines.push_back(L);

        history.push_back({ false, L, newBubble, willPushBubble });
    }

    void rollback(int cp) {
        while ((int)history.size() > cp) {
            HistEntry he = history.back();
            history.pop_back();
            if (!he.isPop) {
                if (he.addedBubble) {
                    if (!bubble.empty()) bubble.pop_back();
                }
                if (!lines.empty()) lines.pop_back();
            } else {
                lines.push_back(he.ln);
                bubble.push_back(he.bubble);
            }
        }
    }

    ll getVal(long long x) const {
        if (lines.empty()) return 0;
        int pos = int(lower_bound(bubble.begin(), bubble.end(), (long double)x) - bubble.begin());
        return lines[pos].eval(x);
    }
};

struct Edge {
    int v;
    ll w;
    Edge() : v(0), w(0) {}
    Edge(int V, ll W) : v(V), w(W) {}
};

int n;
vector<Edge> graph[MAXN];
vector<ll> S, Vv;
vector<ll> distancia;
vector<ll> dp;

void setup_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(FNAME ".inp", "r")) {
        freopen(FNAME ".inp", "r", stdin);
        freopen(FNAME ".out", "w", stdout);
    }
}

void init() {
    cin >> n;
    for (int i = 1; i <= n; ++i) graph[i].clear();
    for (int i = 1; i < n; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        graph[u].push_back(Edge(v, w));
        graph[v].push_back(Edge(u, w));
    }
    S.assign(n + 1, 0);
    Vv.assign(n + 1, 0);
    for (int i = 2; i <= n; ++i) cin >> S[i] >> Vv[i];
}

void dfsCalDis(int u = 1, int pre = -1) {
    for (auto &e : graph[u]) {
        if (e.v == pre) continue;
        distancia[e.v] = distancia[u] + e.w;
        dfsCalDis(e.v, u);
    }
}

void dfsDP(int u, int pre, MinHull &cht) {
    dp[u] = cht.getVal(Vv[u]) + distancia[u] * Vv[u] + S[u];

    int cp = cht.checkpoint();
    cht.addLine(-distancia[u], dp[u]);

    for (auto &e : graph[u]) {
        if (e.v == pre) continue;
        dfsDP(e.v, u, cht);
    }

    cht.rollback(cp);
}

int main() {
    setup_io();
    init();

    distancia.assign(n + 1, 0);
    dfsCalDis();

    dp.assign(n + 1, 0);
    MinHull cht;
    dfsDP(1, -1, cht);

    for (int i = 2; i <= n; ++i) {
        cout << dp[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

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

harbingers.cpp: In function 'void setup_io()':
harbingers.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(FNAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(FNAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100