Submission #1242314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242314		thanhcodedao	Harbingers (CEOI09_harbingers)	C++17	60 / 100	55 ms	17988 KiB

harbingers

/****ThanhCodeDao*****/
/*******Azazel*******/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 21
typedef long long ll;
const ll maxN = 1e5+3, modd = 1e9+7;
struct Point{
    ll x,y;
};
ll cross(Point p,Point q,Point r){ // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
    ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
ll dot(Point vecA,Point vecB){ // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
    ll val = vecA.x*vecB.x + vecA.y*vecB.y;
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
double triarea(Point p,Point q,Point r){ // cross(pq * pr) / 2
    double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    return fabs(cross)/2.0;
}
int n;
ll S[maxN],V[maxN];
ll d[maxN], dp[maxN];
int parent[maxN];
vector<pair<int,int>> adj[maxN];
void pre_dfs(int u,int par){
    parent[u] = par;
    for(pair<int,int> pp : adj[u]){
        int v = pp.F, w = pp.S;
        if(v==par) continue;
        d[v] = d[u] + w;
        pre_dfs(v,u);
    }
}
namespace sub1{
    ll cost(int u,int v){
        return V[v]*(d[v] - d[u]) + S[v];
    }
    void dfs(int u,int par){
        for(pair<int,int> pp : adj[u]){
            int v = pp.F, w = pp.S;
            if(v==par) continue;
            int vv = v;
            while(vv != 0){
                dp[v] = min(dp[v],dp[vv] + cost(vv,v));
                vv = parent[vv];
            }
            dfs(v,u);
        }
    }
    void solve(){
        dfs(1,0);
        for(int i = 2;i<=n;i++) cout << dp[i] << " ";
    }
}

namespace sub2{
    struct Line{
        ll a,b;
    } good[maxN],lines[maxN];
    double e[maxN];
    int k = 0;

    double gd(Line l1,Line l2){
        assert((l1.a - l2.a)!=0);
        return double(l2.b - l1.b) / double(l1.a - l2.a);
    }
    bool isdelete(Line l1,Line l2,Line l3){
        if(l2.a == l3.a) return (l2.b >= l3.b);
        if(k==1) return false;
        double x1 = gd(l1,l2);
        double x2 = gd(l1,l3);
        return x2 <= x1;
    }
    void upl(Line val){
        while(k>=1 and isdelete(good[k-1],good[k],val)){
            --k;
        }
        good[++k] = val;
        if(k>=2) e[k-1] = gd(good[k-1],good[k]);
        e[k] = 1e18;
    }
    Line getl(ll x){
        int best = lower_bound(e+1,e+1+k,x) - e;
        return good[best];
    }
    void dfs(int u,int par){
        Line f = getl(V[u]);
        dp[u] = V[u] * d[u] + V[u]*f.a + S[u] + f.b;
        lines[u].a = -d[u], lines[u].b = dp[u];
        upl(lines[u]);
        for(pair<int,int> pp : adj[u]){
            int v = pp.F;
            if(v==par) continue;
            dfs(v,u);
        }
    }
    void calc(int s){
        k = 0;
        lines[0] = {0,0};
        upl(lines[0]);
        dfs(s,1);
    }
    void solve(){
        for(pair<int,int> pp : adj[1]){
            int u = pp.F;
            calc(u);
        }
        for(int i = 2;i<=n;i++) cout << dp[i] << " ";

    }
}
void solve() {
    cin >> n;
    for(int i = 2;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];
        dp[i] = 1e18;
    }
    pre_dfs(1,0);
    if(n<=2500){
        sub1::solve();
        return;
    }
    sub2::solve();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}

• Subtask 1: 60 / 100