Submission #731106

#	Time	Username	Problem	Language	Result	Execution time	Memory
731106		anha3k25cvp	Harbingers (CEOI09_harbingers)	C++14	10 / 100	1087 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const ll inf = 7 + 1e15;

struct T {
    ll s, v;
};

struct Line {
    ll a, b;
};

int m = 0;
vector <T> e;
vector <Line> L;
vector <dl> x;
vector <int> s;
vector <ll> f, h, p, q;
vector <vector <II>> g;

bool check(int i) {
    int u = s[m];
    if (L[i].a == L[u].a)
        return false;
    if (m == 1)
        return true;
    int v = s[m - 1];
    dl sm = (dl)(L[i].b - L[u].b) / (L[u].a - L[i].a),
       sn = (dl)(L[i].b - L[v].b) / (L[v].a - L[i].a);
    return sn < sm;
}

void dfs(int u) {
    if (m > 0) {
        int i = upper_bound(x.begin(), x.begin() + m + 1, e[u].v) - x.begin() - 1;
        f[u] = h[u] * e[u].v + e[u].s + p[i] * e[u].v + q[i];
    }
    L[u] = {-h[u], f[u]};
    stack <int> pq;
    while (m > 0 && !check(u)) {
        pq.push(s[m]);
        m --;
    }
    s[++ m] = u;
    if (m == 1) {
        x[0] = -inf; p[0] = L[s[1]].a; q[0] = L[s[1]].b;
        x[1] = inf;
    }
    else {
        x[m - 1] = (dl)(L[s[m]].b - L[s[m - 1]].b) / (L[s[m - 1]].a - L[s[m]].a);
        p[m - 1] = L[s[m]].a; q[m - 1] = L[s[m]].b;
        x[m] = inf;
    }
    for (auto z : g[u]) {
        int v = z.st;
        ll w = z.nd;
        if (h[v] < 0) {
            h[v] = h[u] + w;
            dfs(v);
        }
    }
    m --;
    while (!pq.empty()) {
        s[++ m] = pq.top(); pq.pop();
        if (m == 1) {
            x[0] = -inf; p[0] = L[s[1]].a; q[0] = L[s[1]].b;
            x[1] = inf;
        }
        else {
            x[m - 1] = (dl)(L[s[m]].b - L[s[m - 1]].b) / (L[s[m - 1]].a - L[s[m]].a);
            p[m - 1] = L[s[m]].a; q[m - 1] = L[s[m]].b;
            x[m] = inf;
        }
    }
}

int main() {
#define TASKNAME "harbingers"
    ios_base::sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n;
    cin >> n;
    g.resize(n + 1);
    for (int i = 1; i < n; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    e.resize(n + 1);
    for (int i = 2; i <= n; i ++)
        cin >> e[i].s >> e[i].v;
    h.assign(n + 1, -1);
    f.assign(n + 1, 0);
    x.assign(n + 1, 0);
    p.assign(n + 1, 0);
    q.assign(n + 1, 0);
    s.assign(n + 1, 0);
    L.resize(n + 1);
    h[1] = 0;
    dfs(1);
    for (int i = 2; i <= n; i ++)
        cout << f[i] << ' ';
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:91:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:92:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100