Submission #1123410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123410		TVSown	Harbingers (CEOI09_harbingers)	C++20	100 / 100	101 ms	22596 KiB

harbingers

///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);

const int N = 1e5 + 5, MAX = 1e9 + 5, MOD = 1e9 + 7;
int n, k;
int a[N], b[N], d[N];
long long dp[N];
double  pt[N];
struct line{
    long long a, b;
} l[N], s[N];

vector<pi> e[N];

double dis(line A, line B){
    return (-1.0 * (A.b - B.b) / (A.a - B.a));
}

int check(line A, int m){
    double x1 = dis(A, s[m - 1]);
    double x2 = dis(s[m], s[m - 1]);
    return x1 < x2;
}

int pos(line ln){
    int l = 2, r = k;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(ln, mid)){
            r = mid - 1;
        }else l = mid + 1;
    }
    return r + 1;
}

void dfs(int u, int p){
    if(u == 1){
        for(auto [v, w] : e[u]){
            if(v == p) continue;

            d[v] = d[u] + w;
            dfs(v, u);
        }
        return;
    }

    int id = lower_bound(pt + 1 , pt + 1 + k, b[u]) - pt;
    dp[u] = 1ll * d[u] * b[u] - (s[id].a * b[u] + s[id].b) + a[u];
    l[u] = {d[u], -dp[u]};


    int old_k = k, old_pos = k = pos(l[u]);
    line old_line = s[old_pos];
    double old_pt1 = pt[old_pos - 1], old_pt2 = pt[old_pos];
//    cout << u << " " << o
    s[old_pos] = l[u];
    pt[old_pos - 1] = dis(s[old_pos - 1], s[old_pos]);
    pt[old_pos] = 1.0e18;

    for(auto [v, w] : e[u]){
        if(v == p) continue;

        d[v] = d[u] + w;
        dfs(v, u);
    }

    k = old_k;
    s[old_pos] = old_line;
    pt[old_pos - 1] = old_pt1;
    pt[old_pos] = old_pt2;

}

void solve(){
    cin >> n;
    for(int i = 2; i <= n; ++i){
        int u, v, w; cin >> u >> v >> w;
        e[u].pb({v, w});
        e[v].pb({u, w});
    }
    for(int u = 2; u <= n; ++u){
        cin >> a[u] >> b[u];
    }
    s[++k] = {0, 0};
    pt[k] = 1.01e18;

    dfs(1, 0);
    for(int u = 2; u <= n; ++u){
        cout << dp[u] << " ";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inp("in.txt");
//    out("out.txt");
    solve();
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:14:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:109:5: note: in expansion of macro 'inp'
  109 |     inp("in.txt");
      |     ^~~

• Subtask 1: 100 / 100