Submission #1282425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282425		PanosPask	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	27088 KiB

harbingers

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

ll ceil(ll a, int b) {
    return (a + b - 1) / b;
}

struct Line {
    // ax + b = 0
    int a;
    ll b;

    ll eval(ll v) {
        return a * v + b;
    }
    // Returns ceil of intersection
    ll intersect(Line l) {
        return ceil(l.b - b, a - l.a);
    }
};

int N;
vector<vector<pi>> adj_list;
vector<int> S, V;
vector<int> dist;

// dp[node]: Answer for node
vector<ll> dp;

vector<Line> hull;

void calculate(int node, int par) {
    // Binary search on hull to find optimal line
    int l = 0; // ans >= l
    int r = hull.size(); // ans < l

    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (hull[mid].eval(V[node]) <= hull[mid - 1].eval(V[node])) {
            l = mid;
        }
        else {
            r = mid;
        }
    }

    dp[node] = S[node] + (ll)dist[node] * V[node] + hull[l].eval(V[node]);

    // Insert current line and remove everything necessary (don't forget to store)
    Line cur = {-dist[node], dp[node]};

    vector<Line> remaining;
    int sz = hull.size();
    while (sz >= 2) {
        if (hull[sz - 2].intersect(hull[sz - 1]) >= hull[sz - 1].intersect(cur)) {
            // We start using cur instead of hull[sz - 1] before using hull[sz - 1] instead of hull[sz - 2]
            remaining.push_back(hull.back());
            hull.pop_back();
            sz--;
        }
        else {
            break;
        }
    }
    hull.pb(cur);

    for (auto [neigh, w] : adj_list[node]) {
        if (neigh == par) {
            continue;
        }

        dist[neigh] = dist[node] + w;
        calculate(neigh, node);
    }

    // Remove last line and re-insert previous ones
    hull.pop_back();
    while (!remaining.empty()) {
        hull.pb(remaining.back());
        remaining.pop_back();
    }
}

int main(void) {
    scanf("%d", &N);

    adj_list.resize(N);
    S.resize(N);
    V.resize(N);
    dist.resize(N);
    dp.resize(N);   

    for (int i = 0; i < N - 1; i++) {
        int u, v, d;
        scanf("%d %d %d", &u, &v, &d);
        u--; v--;

        adj_list[u].pb(mp(v, d));
        adj_list[v].pb(mp(u, d));
    }
    for (int i = 1; i < N; i++) {
        scanf("%d %d", &S[i], &V[i]);
    }

    dp[0] = 0;
    hull.push_back({0, 0});
    for (auto [neigh, w] : adj_list[0]) {
        dist[neigh] = w;
        calculate(neigh, 0);
    }

    for (int i = 1; i < N; i++) {
        printf("%lld ", dp[i]);
    }
    printf("\n");

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
harbingers.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d %d %d", &u, &v, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d %d", &S[i], &V[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100