Submission #1214897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214897		DangKhoizzzz	Harbingers (CEOI09_harbingers)	C++20	100 / 100	79 ms	25156 KiB

harbingers

#include <bits/stdc++.h>
#define int long long
#define pii pair <int , int>
#define fi first
#define se second

using namespace std;
const int maxn = 1e5+2;
const int INF = 1e18;

struct line
{
    int a , b , p;
    bool operator < (line l) {return a < l.a;}
    bool operator < (int k) {return p < k;}
};

struct Convex_Hull_Trick
{
    int div(int a , int b)
    {
        return a/b - ((a^b) < 0 && a%b);
    }
    void isect(line &l , line y)
    {
        if(l.a == y.a) l.p = (l.b > y.b) ? INF: -INF;
        else l.p = div(y.b - l.b , l.a - y.a);
    }
    vector <line> x;
    void add(line l)
    {
        if(!x.empty()) isect(x.back() , l);
        while(x.size() > 1 && x[x.size()-2].p >= x.back().p)
        {
            x.pop_back();
            isect(x.back() , l);
        }
        x.push_back(l);
    }
    int query(int v)
    {
        if(x.empty()) return -INF;
        line l = *lower_bound(x.begin() , x.end() , v);
        return l.a*v + l.b;
    }
} cht[maxn];

int n , sz[maxn] , head[maxn] , parent[maxn], dp[maxn];
vector <pii> g[maxn];

void pre_dfs(int u , int p)
{
    sz[u] = 1;
    parent[u] = p;
    for(pii tmp: g[u])
    {
        int v = tmp.fi , w = tmp.se;
        if(v == p) continue;
        pre_dfs(v , u);
        sz[u] += sz[v];
    }
}

void decompose(int u , int p)
{
    int mx = -1;

    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i].fi;
        int w = g[u][i].se;
        if(v == p) continue;
        if(mx == -1) mx = i;
        else if(sz[g[u][mx].fi] < sz[v]) mx = i;
    }
    if(mx == -1) return;
    pii tmp = g[u][mx];
    g[u].erase(g[u].begin() + mx);
    g[u].push_back(tmp);

    for(int i = 0; i < g[u].size() - 1; i++)
    {
        int v = g[u][i].fi;
        int w = g[u][i].se;
        if(v == p) continue;
        head[v] = v;
        decompose(v , u);
    }
    head[g[u].back().fi] = head[u];
    decompose(g[u].back().fi , u);
}

int S[maxn] , V[maxn];


int find_mn(int u , int v)
{
    int res = INF;
    while(u != 0)
    {
        u = head[u];
        res = min(res , -cht[u].query(v));
        u = parent[u];
    }
    return res;
}

void dfs(int u , int p , int pre)
{
    dp[u] = pre*V[u] + S[u];
    if(u != 1) dp[u] += find_mn(u , V[u]);
    cht[head[u]].add({pre , -dp[u] , INF});
    for(pii tmp: g[u])
    {
        int v = tmp.fi;
        int w = tmp.se;
        if(v == p) continue;
        dfs(v , u  , pre + w);
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    for(int i = 2; i <= n; i++)
    {
        cin >> S[i] >> V[i];
    }
    head[1] = 1;
    pre_dfs(1 , 0);
    decompose(1 , 0);
    dfs(1 , 1 , 0 );
    for(int i = 2; i <= n; i++) cout << dp[i] << ' ';
}

signed 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: 100 / 100