Submission #1254170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254170		VKhang	Harbingers (CEOI09_harbingers)	C++20	100 / 100	61 ms	17584 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define fi first
#define se second
struct Line{
    long long m,b;
};
struct SAVE{
    int x;
    int y;
    Line z;
};
int n;
vector <pair <int,int>> s[N];
vector <SAVE> Save;
int a[N], b[N];
long long d[N];
long long dp[N];
int Size = 0;
Line line[N];
bool bad(Line l1, Line l2, Line l3){
    return (((double)(l1.b - l2.b) / (l2.m - l1.m)) >= ((double)(l1.b - l3.b) / (l3.m - l1.m)));
}
long long calc(int x, int id){
    return 1ll * line[id].m * x + line[id].b;
}
void add_Line(long long m, long long b){
    int l = 2, r = Size;
    int id = Size + 1;
    Line newLine = {m, b};
    while(l <=   r){
        int mid = (l + r)/2;
        if (bad(line[mid - 1], line[mid], newLine)){
            id = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    Save.push_back({id, Size, line[id]});
    Size = id;
    line[id] = newLine;
}
long long Query(int x){
    int l = 1, r = Size;
    long long ans = 1e18;
    while (l <= r){
        int mid = (l + r)/2;
        long long u, v;
        u = calc(x, mid);
        if (mid + 1 <= Size) v = calc(x, mid + 1);
        else v = 1e18;
        if (u >= v) l = mid + 1;
        else r = mid - 1;
        ans = min({ans, u, v});
    }
    return ans;
}
void undo(){
    int id = Save.back().x;
    int re_size = Save.back().y;
    Line old_line = Save.back().z;
    line[id] = old_line;
    Size = re_size;
    Save.pop_back();
}
void dfs(int i, int pre){
    if (i != pre){
        dp[i] = a[i] + 1ll * d[i] * b[i] + Query(b[i]);
    }
    add_Line( -d[i], dp[i]);
    for (auto x: s[i]){
        if (x.fi == pre)
            continue;
        d[x.fi] = d[i] + x.se;
        dfs(x.fi, i);
    }
    undo();
}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++){
        int u,v,w;
        cin >> u >> v >> w;
        s[u].push_back({v,w});
        s[v].push_back({u,w});
    }
    for (int i = 2; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    dfs(1, 1);
    for (int i = 2; i <= n; i++){
        cout << dp[i] << " ";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 100 / 100