Submission #1123537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123537		LTTrungCHL	Harbingers (CEOI09_harbingers)	C++20	0 / 100	116 ms	24052 KiB

harbingers

///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
//vector <int> lg2;
//void LOG_ARR(int n){
//    lg2.resize(n + 3);
//    for (int i = 1;i <= n;++i){
//        lg2[i] = __lg(i);
//    }
//}
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
int n;
int s[N], v[N];
struct line{
    long long a, b;
};
line c[N];
long double giao[N];
vector <pair <int ,int>> adj[N];
int sz;
long long d[N];
long long dp[N];
long long query(int x){
    int l = 1, r = sz;
    int res = 0;
    while (l <= r){
        int mid = (l + r)/2;
        if (giao[mid] <= x){
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
//    return res;
    if (res - 1)
    return c[res].a * x + c[res].b;
    return 0;
}
bool b_isbad(line a, line b, line c){
    return 1.0 * (c.b - a.b)/(a.a - c.a) < 1.0 * (b.b - a.b)/(a.a - b.a);
}
long double insec(line a, line b){
    return 1.0 * (b.b - a.b)/(a.a - b.a);
}
int findsz(line x){
    if (sz == 1 or  !b_isbad(c[sz - 1], c[sz], x)){
        return sz + 1;
    }
    int l = 2, r = sz;
    int res = sz;
    while (l <= r){
        int mid = (l + r)/2;
        if (b_isbad(c[mid - 1], c[mid], x)){
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
    return res;
}
void dfs(int u, int p){
    dp[u] = query(v[u]) + s[u] + d[u] * v[u];
//    cout << u <<" "<< sz <<" "<<query(v[u]) <<" "<< giao[1] <<" "<< d[u]  <<"\n";
    int tmpsz = sz;
    sz = findsz({-d[u], dp[u]});
    line tmp = c[sz];
    c[sz] = {-d[u], dp[u]};
    long double tmpgiao = giao[sz];
    giao[sz] = insec(c[sz], c[sz - 1]);
    for (int i = 0;i < adj[u].size();++i){
        int v = adj[u][i].F;
        int w = adj[u][i].S;
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
    }
    giao[sz] = tmpgiao;
    c[sz] = tmp;
    sz = tmpsz;
    return;
}
void solve(){
    cin >> n;
    for (int i = 1;i < n;++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (int i = 2;i <= n;++i){
        cin >> s[i] >> v[i];
    }
    dfs(1, 0);
    for (int i = 2;i <= n;++i){
        cout << dp[i] << " ";
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("npt.inp", "r")){
        freopen("npt.inp", "r", stdin);
        freopen("npt.out", "w", stdout);
    }
//    int t;
//    cin >> t;
//    while(t--){
    solve();
//    }
    return 0;
}



///////////////////////

Compilation message (stderr)

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

• Subtask 1: 0 / 100