제출 #644382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
644382		SOCIOPATE	Harbingers (CEOI09_harbingers)	C++17	50 / 100	1097 ms	44628 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;
    mutable function<const line*()> succ;
    bool operator<(const line otherline) const{
        if(otherline.b == INF){
            auto nxt = succ();
            if(!nxt) return 0;
            return calcx(nxt->b - b, k - nxt->k) <= otherline.k;
        }
        if(otherline.k == k) return b < otherline.b;
        return k > otherline.k;
    }
};

struct chl : multiset<line>{
    bool badline(iterator y){
        if(y == begin() || next(y) == end()) return 0;
        ll point1, point2;
        point1 = calcx(y->b - prev(y)->b, prev(y)->k - y->k);
        point2 = calcx(next(y)->b - y->b, y->k - next(y)->k);
        return point1 >= point2;
    }
    bool addline(ll k, ll b, ll id){
        auto y = insert({k, b, id});
        if(y != begin() && prev(y)->k == k){
            erase(y);
            return 0;
        }
        if(next(y) != end() && next(y)->k == k){
            reset[cur].push_back(next(y)->id);
            erase(next(y));
        }
        if(badline(y)){
            erase(y);
            return 0;
        }
        y->succ = [=](){return next(y) == end() ? 0 : &*next(y);};
        while(y != begin() && badline(prev(y))){
            reset[cur].push_back(prev(y)->id);
            erase(prev(y));
        }
        while(next(y) != end() && badline(next(y))){
            reset[cur].push_back(next(y)->id);
            erase(next(y));
        }
        return 1;
    }
    ll query(ll x, ll id){
        const line l = *lower_bound({x, INF, id});
        return l.k*x + l.b;
    }
    void printlines(){
        auto y = begin();
        while(y != end()){
            cout << y->k << ' ' << y->b << ' ' << y->id << '\n';
            y = next(y);
        }
    }
};

chl hull;

void dfs(int v, int p, ll d){
    dist[v] = d;
    cur = v;
    if(v) ans[v] = hull.query(vv[v], v) + dist[v]*vv[v] + s[v];
    bool y = hull.addline(-dist[v], ans[v], v);
    for(pll& u : a[v]){
        if(u.ff == p) continue;
        dfs(u.ff, v, d + u.ss);
    }
    if(y) hull.erase({-dist[v], ans[v], v});
    for(int u : reset[v]) hull.addline(-dist[u], ans[u], u);
}

void solve(){
    cin >> 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