Submission #882107

#	Time	Username	Problem	Language	Result	Execution time	Memory
882107		Flan312	Harbingers (CEOI09_harbingers)	C++17	100 / 100	97 ms	24812 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const ll oo = 1e18;
int n, s[nmax], v[nmax];
vector <pii> adj[nmax];
ll dist[nmax], dp[nmax];
struct segment
{
    ll a, b;
    segment(ll a = 0, ll b = 0) : a(a), b(b) {}
} lst[nmax];
int m = 0;
struct persistent
{
    int id, old_m;
    segment old_line;
    persistent(int id, int old_m, const segment& old_line): id(id), old_m(old_m), old_line(old_line) {}
};
stack <persistent> st;
double intersect(const segment &x, const segment &y)
{
    return 1.0 * (y.b - x.b) / (x.a - y.a);
}
void add(const segment &x)
{
    int l = 2, r = m, ans = m + 1;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if (intersect(lst[mid - 1], x) <= intersect(lst[mid - 1], lst[mid]))
            ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    st.emplace(ans, m, lst[ans]);
    m = ans;
    lst[m] = x;
}
void undo()
{
    auto [id, old_m, old_line] = st.top();
    st.pop();
    m = old_m;
    lst[id] = old_line;
}
ll get(int x)
{
    int l = 2, r = m, ans = 1;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if (intersect(lst[mid - 1], lst[mid]) <= x)
            ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return 1ll * lst[ans].a * x + lst[ans].b; 
}
void dfs(int u, int par = -1)
{
    if (u != 1)
        dp[u] = get(v[u]) + 1ll * dist[u] * v[u] + s[u];
    add({-dist[u], dp[u]});
    for (auto &[w, v] : adj[u])
    {
        if (v == par) continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
    undo();
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n;
    for (int u, v, w, i = 1; i < n; ++i)
    {
        cin >> u >> v >> w;
        adj[u].eb(w, v);
        adj[v].eb(w, u);
    }
    for (int i = 2; i <= n; ++i)
        cin >> s[i] >> v[i];
    dfs(1);
    for (int i = 2; i <= n; ++i)
        cout << dp[i] << ' ';
}

Compilation message (stderr)

harbingers.cpp: In function 'void add(const segment&)':
harbingers.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                   ~~^~~
harbingers.cpp: In function 'long long int get(int)':
harbingers.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int mid = l + r >> 1;
      |                   ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:83:31: note: in expansion of macro 'nx'
   83 |     if (ifstream(task".inp")) nx
      |                               ^~
harbingers.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:83:31: note: in expansion of macro 'nx'
   83 |     if (ifstream(task".inp")) nx
      |                               ^~

• Subtask 1: 100 / 100