Submission #644401

#	Time	Username	Problem	Language	Result	Execution time	Memory
644401		SOCIOPATE	Harbingers (CEOI09_harbingers)	C++17	50 / 100	429 ms	65536 KiB

harbingers

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()

typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordset;

#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")

ll INF = 2e18;
const ll mod = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow(ll n, ll m){
    if(!m) return 1;
    if(m & 1) return (n * binpow(n, m - 1)) % mod;
    ll b = binpow(n, m / 2);
    return (b*b) % mod;
}

int n, cur;

vector<ll> dist, s, vv, ans;
vector<vector<int>> reset;
vector<vector<pll>> a;

ll calcx(ll a, ll b){
    ll delta = (bool)(a % b);
    if((a > 0 && b > 0) || (a < 0 && b < 0)) return a / b + delta;
    return a / b;
}

struct line{
    ll k, b, id;
};

vector<line> hull;

void addline(ll k, ll b, ll id){
    while((int)hull.size() >= 2){
        if(calcx(hull.back().b - hull[hull.size() - 2].b, hull[hull.size() - 2].k - hull.back().k) >= calcx(b - hull.back().b, hull.back().k - k)){
            reset[cur].emplace_back(hull.back().id);
            hull.pop_back();
        } else break;
    }
    hull.push_back({k, b, id});
}

ll query(ll x){
    int l = 0, r = (int)hull.size() - 2, pos = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        ll point = calcx(hull[mid + 1].b - hull[mid].b, hull[mid].k - hull[mid + 1].k);
        if(point <= x){
            pos = mid + 1;
            l = mid + 1;
        } else r = mid - 1;
    }
    return hull[pos].k*x + hull[pos].b;
}

void dfs(int v, int p, ll d){
    dist[v] = d;
    cur = v;
    if(v) ans[v] = query(vv[v]) + dist[v]*vv[v] + s[v];
    addline(-dist[v], ans[v], v);
    for(pll& u : a[v]){
        if(u.ff == p) continue;
        dfs(u.ff, v, d + u.ss);
    }
    //assert((int)hull.size() > 0);
    hull.pop_back();
    for(int i = (int)reset[cur].size() - 1; i >= 0; i--){
        int u = reset[cur][i];
        addline(-dist[u], ans[u], u);
    }
}

void solve(){
    cin >> n;
    hull.reserve(n);
    ans.resize(n);
    a.resize(n);
    reset.resize(n);
    vv.resize(n);
    s.resize(n);
    dist.resize(n, 0);
    for(int i = 0; i < n - 1; i++){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--; v--;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    for(int i = 1; i < n; i++) cin >> s[i] >> vv[i];
    dfs(0, -1, 0);
    for(int i = 1; i < n; i++) cout << ans[i] << ' ';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
//    freopen("harbingers.in", "r", stdin);
//    freopen("harbingers.out", "w", stdout);
	int tt;
    //cin >> tt;
	tt = 1;
	while (tt--) {
		solve();
		#ifdef LOCAL
            cout << "__________________________________" << endl;
		#endif
	}
	#ifdef LOCAL
        cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << "sec" << '\n';
	#endif
	return 0;
}

• Subtask 1: 50 / 100