Submission #1176822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176822		YugiHacker	Harbingers (CEOI09_harbingers)	C++17	100 / 100	71 ms	17584 KiB

harbingers

/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 100005
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

int n, S[maxn], V[maxn];
vector <pii> adj[maxn];
long long dp[maxn], depth[maxn];

struct Line {
    long long a, b;
    long long cal(long long x) const{return a*x + b;}
};
int top;
Line lines[maxn];
struct save{int pos, cur_top; Line L;};

vector<save> roll_backs;

bool check(Line &A, Line &B, Line &C) {
    return (double) (A.b - B.b) * (C.a - B.a) >= (double) (C.b - B.b) * (A.a - B.a); /// convex find min
}
void add(Line L) {
    int l = 0, r = top;
    while (r - l > 1)
    {
        int m = (l + r) / 2;
        if (check(lines[m-1], lines[m], L)) r = m;
        else l = m;
    }
    roll_backs.push_back(save{r, top, lines[r]});
    top = r + 1;
    lines[r] = L;
}
long long query(long long x) {
    int l = 0, r = top - 1;
    while (r - l > 2)
    {
        int m1 = (l + r) / 2;
        int m2 = m1 + 1;
        if (lines[m1].cal(x) >= lines[m2].cal(x))
            l = m1;
        else r = m2;
    }
    long long ans = 1e18;
    for (int i=l; i<=r; i++) ans = min(ans, lines[i].cal(x));
    return ans;
}

void roll_back() {
    auto Save = roll_backs.back();
    int pos = Save.pos;
    top = Save.cur_top;
    lines[pos] = Save.L;
    roll_backs.pop_back();
}

/// dp[v] = (depth[v] - depth[u]) * V[v] + dp[u] + S[v]
/// dp[v] = -depth[u] * V[v] + dp[u] + S[v] + depth[v] * V[v];
void dfs(int u, int p=-1){
    if (u > 1) dp[u] = query(V[u]) + S[u] + depth[u] * V[u];

    add(Line({-depth[u], dp[u]}));

    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + w;
        dfs(v, u);
    }
    roll_back();
}

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    f1 (i, n-1)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    f1 (i, n-1) cin >> S[i+1] >> V[i+1];
    dfs(1);
    f1 (i, n-1) cout << dp[i+1] << ' ';
}

Compilation message (stderr)

harbingers.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main()
      | ^~~~

• Subtask 1: 100 / 100