제출 #1266861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266861		luis_aqm	Harbingers (CEOI09_harbingers)	C++20	100 / 100	68 ms	19600 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define NMAX 100005
#define INF 1e16
#define MOD 998244353
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

vector<pii> g[NMAX];
int s[NMAX], t[NMAX], dist[NMAX], dp[NMAX];
int hull[NMAX];
int ptr;

double intersecx(int i, int j) {
    return 1.0 * (dp[i] - dp[j]) / (dist[i] - dist[j]);
}

void DFS(int v, int pai) {
    int aux = 0, sz = ptr;
    if(v != 1) {
        int l = 0, r = ptr-1;
        while(l < r) {
            int q = (r-l) / 3;
            int m1 = l+q, m2 = r-q;

            if(dp[hull[m1]] - dist[hull[m1]]*t[v] < dp[hull[m2]] - dist[hull[m2]]*t[v])
                r = m2-1;
            else l = m1+1;
        }

        dp[v] = dp[hull[r]] + (dist[v] - dist[hull[r]]) * t[v] + s[v];

        l = 1, r = ptr;
        while(l < r) {
            int m = (l+r) / 2;

            int j = hull[m], k = hull[m-1];
            if(intersecx(v, j) < intersecx(j, k))
                r = m;
            else l = m+1;
        }

        aux = hull[r];
        hull[r] = v;
        ptr = r+1;
    }
    else {
        hull[0] = 1;
        ptr = 1;
    }

    for(auto [u, d] : g[v]) {
        if(u == pai) continue;

        dist[u] = dist[v] + d;
        DFS(u, v);
    }
    
    hull[ptr-1] = aux;
    ptr = sz;
}

int32_t main(){ faster
    int n;
    cin>>n;

    for(int i = 1; i < n; i++) {
        int a, b, c;
        cin>>a>>b>>c;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    for(int i = 2; i <= n; i++) {
        cin>>s[i]>>t[i];
    }

    DFS(1, 0);

    for(int i = 2; i <= n; i++) {
        cout<<dp[i]<<" ";
    }
    cout<<"\n";
}
/*


*/

• Subtask 1: 100 / 100