Submission #319905

#	Time	Username	Problem	Language	Result	Execution time	Memory
319905		BeanZ	Harbingers (CEOI09_harbingers)	C++14	100 / 100	143 ms	22372 KiB

harbingers

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
//#define task "A"
#define ll long long
#define endl '\n'
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
struct Point{
    ll x, y;
    Point(){};
    Point(ll x, ll y) : x(x), y(y){};
};
ll sz = 1;
vector<pair<ll, ll>> node[N];
Point line[N];
long double Intersex(Point l1, Point l2){
    return (l2.y - l1.y) * 1.0 / (l1.x - l2.x);
}
bool chk(Point lnow, Point l1, Point l2){
    return (Intersex(lnow, l2) <= Intersex(l1, l2));
}
ll add(Point m){
    ll l = 2, h = sz;
    while (l <= h){
        ll mid = (l + h) >> 1;
        Point l1 = line[mid];
        Point l2 = line[mid - 1];
        if (chk(m, l1, l2)) h = mid - 1;
        else l = mid + 1;
    }
    return l;
}
ll get(Point x, ll now){
    return x.x * now + x.y;
}
ll query(ll x){
    ll l = 1, h = sz - 1;
    while (l <= h){
        ll mid = (l + h) >> 1;
        if (get(line[mid], x) <= get(line[mid + 1], x)) l = mid + 1;
        else h = mid - 1;
    }
    return get(line[l], x);
}
ll dp[N], a[N], b[N], dep[N];
void dfs(ll u, ll p){
    ll tmp = sz;
    ll id;
    Point tmpP;
    if (p){
        dp[u] = a[u] + dep[u] * b[u] - query(b[u]);
        Point cur = {dep[u], -dp[u]};
        id = add(cur);
        tmpP = line[id];
        sz = id;
        line[id] = cur;
    }
    for (auto j : node[u]){
        if (j.first == p) continue;
        dep[j.first] = dep[u] + j.second;
        dfs(j.first, u);
    }
    if (p){
        line[id] = tmpP;
        sz = tmp;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i < n; i++){
        ll u, v, c;
        cin >> u >> v >> c;
        node[u].push_back({v, c});
        node[v].push_back({u, c});
    }
    for (int i = 2; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    line[1] = {0, 0};
    dfs(1, 0);
    for (int i = 2; i <= n; i++) cout << dp[i] << " ";
}
/*
*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100