Submission #1042141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042141		khanhtb	Harbingers (CEOI09_harbingers)	C++14	0 / 100	80 ms	65536 KiB

harbingers

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7; 
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 1e5+8;
struct Li_Chao_Tree{
    const ll l = -1e9, r = 1e9;
    struct line{
        ll a,b;
        line(ll a, ll b):a(a),b(b){};
        ll operator()(ll x){
            return a*x+b;
        }
    };
    struct node{
        ll left,right;
        line y;
        node():left(0),right(0),y(line(0,inf)){};
    };
    vector<node> st = {node(),node()};
    void addline(ll id, ll l, ll r, line nl){
        ll m = l+r>>1;
        bool lck = st[id].y(l) > nl(l);
        bool mck = st[id].y(m) > nl(m);
        bool rck = st[id].y(r) > nl(r);
        if(mck) swap(st[id].y,nl);
        if(l == r) return;
        if(lck != mck){
            if(!st[id].left) st[id].left = st.size(), st.pb(node());
            addline(st[id].left,l,m,nl);
        }
        else if(rck != mck){
            if(!st[id].right) st[id].right = st.size(), st.pb(node());
            addline(st[id].right,m+1,r,nl);
        }
    }
    ll query(ll id, ll l, ll r, ll x){
        ll m = l+r>>1, val = st[id].y(x);
        if(l == r) return val;
        if(x <= m && st[id].left) val = min(val,query(st[id].left,l,m,x));
        if(x > m && st[id].right) val = min(val,query(st[id].right,m+1,r,x));
        return val;
    }
    void update(ll a, ll b){
        addline(1,l,r,line(a,b));
    }
    ll get(ll x){
        return query(1,l,r,x);
    }
} lct[N<<2];
void update(ll id, ll l, ll r, ll i, ll a, ll b){
    if(i < l || r < i) return;
    lct[id].update(a,b);
    if(l == r) return;
    ll m = l+r>>1;
    update(id<<1,l,m,i,a,b);
    update(id<<1|1,m+1,r,i,a,b);
}
ll get(ll id, ll l, ll r, ll u, ll v, ll x){
    if(v < l || r < u) return inf;
    if(u <= l && r <= v) return lct[id].get(x);
    ll m = l+r>>1;
    return min(get(id<<1,l,m,u,v,x),get(id<<1|1,m+1,r,u,v,x));
}
vpll g[N];
ll sz[N],par[N];
ll n;
ll S[N],V[N],d[N];
void cc(ll u, ll p){
    sz[u] = 1;
    for(pll v:g[u]){
        if(v.fi != p){
            par[v.fi] = u;
            d[v.fi] = d[u]+v.se;
            cc(v.fi,u);
            sz[u] += sz[v.fi];
        }
    }
}
ll head[N],chain[N],cp = 1,cch = 1,pos[N];
void hld(ll u, ll p){
    if(!head[cch]) head[cch] = u;
    chain[u] = cch;
    pos[u] = cp;
    cp++;
    ll nxt = 0;
    for(pll v:g[u]){
        if(v.fi == p) continue;
        if(!nxt || sz[v.fi] > sz[nxt]) nxt = v.fi;
    }
    if(nxt) hld(nxt,u);
    for(pll v:g[u]){
        if(v.fi != p && v.fi != nxt){
            cch++;
            hld(v.fi,u);
        } 
    }
}
void upd(ll u, ll a, ll b){
    update(1,1,n,pos[u],a,b);
}
ll query(ll u){
    ll ans = inf;
    while(chain[u] != chain[1]){
        ll val = get(1,1,n,pos[head[chain[u]]],pos[u],V[u]);
        ans = min(ans,val);
        u = par[head[chain[u]]];
    }
    ll val = get(1,1,n,pos[1],pos[u],V[u]);
    ans = min(ans,val);
    return ans;
}
ll dp[N];
void dfs(ll u, ll p){
    if(u != 1) dp[u] = query(u)+d[u]*V[u]+S[u];
    upd(u,-d[u],dp[u]);
    for(pll ed:g[u]){
        ll v = ed.fi;
        if(v == p) continue;
        dfs(v,u);
    }
}
void solve(){
    cin >> n;
    for(ll i = 1; i < n; i++){
        ll u,v,w;cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    for(ll i = 2; i <= n; i++) cin >> S[i] >> V[i];
    cc(1,1);
    hld(1,1);
    dfs(1,1);
    for(ll i = 2; i <= n; i++) cout << dp[i] << " ";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }   
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++) {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

harbingers.cpp: In member function 'void Li_Chao_Tree::addline(long long int, long long int, long long int, Li_Chao_Tree::line)':
harbingers.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         ll m = l+r>>1;
      |                ~^~
harbingers.cpp: In member function 'long long int Li_Chao_Tree::query(long long int, long long int, long long int, long long int)':
harbingers.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         ll m = l+r>>1, val = st[id].y(x);
      |                ~^~
harbingers.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
harbingers.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     ll m = l+r>>1;
      |            ~^~
harbingers.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
harbingers.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     ll m = l+r>>1;
      |            ~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100