Submission #1134026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134026		quangnamoiracvl_ralaidecu	Harbingers (CEOI09_harbingers)	C++17	50 / 100	122 ms	27488 KiB

harbingers

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define endl "\n"
#define fi first
#define se second
#define tn long long
#define pair pair< tn, tn >
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
#define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- )
#define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const tn N = 1e5 + 5;
struct mimi{
    tn rtime, v;
} a[N];
vector<pair> g[N];
tn n, u, v, w, dist[N], dp[N];
inline namespace _LineContainer {
bool _Line_Comp_State;
struct Line {
	// faster LineContainer
	mutable tn k, m, p;
	bool operator<(const Line &o) const { return _Line_Comp_State ? p < o.p : k < o.k; }
};

struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }

	bool isect(iterator x, iterator y) {
		if (y == end()) {
			x->p = LLONG_MAX;
			return false;
		}
		if (x->k == y->k) x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}

	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}

	long long get(long long x) {
		assert(!empty());
		_Line_Comp_State = 1;
		auto l = *lower_bound({0, 0, x});
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};
}
LineContainer CHT;
void removeLine( tn k, tn m ){
    auto it = CHT.find( { k, m, 0 } );
    if ( it != CHT.end() )
        CHT.erase(it);
}
void build_centroid_tree( tn u, tn par ){
    dp[u] = a[u].rtime + a[u].v * dist[u] - CHT.get( a[u].v );
    CHT.add( dist[u], -dp[u] );
    for ( auto v : g[u] ){
        if ( v.fi == par )
            continue;
        if ( CHT.find( { dist[u], -dp[u], 0 } ) == CHT.end() )
            CHT.add( dist[u], -dp[u] );
        dist[v.fi] = dist[u] + v.se;
        build_centroid_tree( v.fi, u );
    }
    removeLine( dist[u], -dp[u] );
}
signed main(){
    cin >> n; CHT.add( 0, 0 );
    thaonguyen( i, 1, n - 1 )
        cin >> u >> v >> w,
        g[u].push_back( { v, w } ),
        g[v].push_back( { u, w } );
    thaonguyen( i, 2, n )
        cin >> a[i].rtime >> a[i].v;
    build_centroid_tree( 1, -1 );
    thaonguyen( i, 2, n )
        cout << dp[i] << " ";
}

• Subtask 1: 50 / 100